[그래픽스] 선 그리기 (브레젠험 알고리즘, 코헨-서더랜드 클리핑 알고리즘)

서론

 

선을 그리는 것은 힘든 일은 아닙니다.

 

점 P1 과 점 P2가 있다고 합시다.

 

위 그림과 같이 식을 전개하면 P1P2 사이의 점 Px 를 구할 수 있습니다.

 

이 공식을 이용해서 직선을 긋는 알고리즘을 한 번 작성해보겠습니다.

 

위 선 그리기 알고리즘을 통해서 삼각형을 하나 그려봤습니다.

이 선 그리기 알고리즘은 꽤나 간단하고 그럴싸해 보이지만 성능상 문제가 존재합니다.

 

일단, t의 증가량을 어떻게 설정해야 할 지 애매하기 때문에 필요 이상으로 점을 많이 찍거나, 혹은 필요 이하로 점을 덜 찍을 가능성이 존재합니다.

 

그 다음은 부동소수점 곱셈으로 연산을 수행하기 때문에 속도가 떨어질 수 있습니다.

 

결국 픽셀좌표 하나하나는 정수 값을 가지기 때문에, 이론상 정수만을 해용해서 선을 그릴 수 있습니다.

 

첫 번째 해결방법은 점 P1과 점 P2의 기울기를 구해서, 점 P1 에서 출발한 점 Px가 P2에 도달할 때까지 기울기를 더해가면서 점을 찍는 것입니다.

 

이는 앞서 선보인 알고리즘보다 확실히 성능상에서 앞서있지만, 여전히 부동소수점 덧셈 연산을 수행한다는 것에서 성능 저하가 발생할 수 있습니다.

 

그렇다면 최적화된 선 그리기 알고리즘은 브레젠험의 알고리즘에 대해서 알아봅시다.

 

브레젠험의 알고리즘

 

직선의 방정식을 통해 그려지는 직선을 정수 값을 가지는 픽셀에 어떻게 하면 효율적이게 표현할 수 있을까요?

브레젠험 직선 알고리즘의 원리는 다음과 같습니다.

 

먼저 좌측위 점에서 우측 아래 점까지 선을 그어보겠습니다.

이번 포스팅에서 구현할 브레젠험의 알고리즘에선 시작점과 도착점이 스크린 좌표로 변환된 형태를 사용합니다.

(즉, 정수값을 가지고 윈도우 좌표계를 사용하는 형태)

 

여기서 그리고자 하는 직선의 넓이 w와 높이 h를 구합니다.

각각 w = 6, h = 4 죠.

 

먼저, 시작 위치에 점을 찍어 봅시다.

그러면 다음에 찍을 점은 위와 같습니다. 

처음 찍은 점과 평행한 점인 (x+1, y) 이냐

처음 찍은 점의 아래 점인 (x+1, y+1) 이냐

 

x값은 x+1 로 고정이지만, y값을 결정하는 것이 이 알고리즘의 핵심입니다.

그러면 이 y값을 선택하기 위해서 (x+1, y+0.5) 를 찍어봅시다.

여기서 시작점~끝점으로 향하는 직선을 그어봅시다.

브레젠험의 알고리즘은 중점이 해당 직선의 방정식보다 위에 있으면

y+1에 점을 찍고, 아래에 있으면 y에 점을 찍습니다.

 

그렇다면 직선의 방정식을 구해봅시다.

 

그렇다면 만약 위에서 구한 직선의 방정식이 y+0.5 보다 작을 경우 (x+1, y) 작으면 (x+1, y+1)에 찍으면 되겠죠?

정리하면 다음과 같습니다. 

 

여기서 t는 x0에서 얼만큼 갔는가를 나타냅니다.

 

만약 t = 1 이라면, 2h - w < 0 라는 판별식에 따라서 점을 찍으면 됩니다.

그러나 그 다음 점은 조금 다릅니다.

 

만약, 초기 점과 평행한 점을 찍었으면 y0 + 0.5 를

아랫점을 찍었으면 y0 + 1.5 를 비교해야 합니다.

 

그렇다면 아래와 같이 두 가지 경우로 나뉩니다.

 

그리고 또 그 다음 점에서는 판별식이 달라집니다.

그렇다면 이 식을 일반화해봅시다.

 

 

그렇다면 아래와 같은 알고리즘으로 정리할 수 있을 것 입니다.

그런데 이 알고리즘으로는 모든 방향으로 직선을 그을 수 없습니다.

이쪽에 해당하는 직선만 그을 수 있죠

해당 영역을 1팔분면 이라고 하며

시계방향으로 2팔분면, 3팔분면, ... 8팔분면까지 존재합니다.

 

그렇다면 2팔분면에서는 어떻게 그어야할지 생각해봅시다.

그런데, x와 y만 변경되었을 뿐 전개 방식은 동일합니다.

즉, x, y와 w, h를 바꿔주면 선을 그을 수 있습니다.

 

나머지도 기본원리는 동일하고 선분의 진행방향만 다릅니다.

이에 유의하여 알고리즘을 완성시켜봅시다.

 

void RenderManager::DrawLine(const Vertex2D& src, const Vertex2D& dst) const
{
	//브레젠험 알고리즘
	ScreenPos startPos = Vector2DToScreenPos(src.Position);
	ScreenPos EndPos = Vector2DToScreenPos(dst.Position);

	int32 w = EndPos.X - startPos.X;
	int32 h = EndPos.Y - startPos.Y;

	//그리고자 하는 직선이 완만한지 급경사인지 판단합니다.
	//true 라면 완만한 경사입니다. 
	bool bDrawFlag = MM::Abs(w) >= MM::Abs(h);

	//x값의 변화량입니다.
	//w가 양수라면 양의 방향으로 뻗습니다.
	int32 dx = (w >= 0) ? 1 : -1;
	int32 dy = (h >= 0) ? 1 : -1;

	//판별식에 사용되는 w와 h는 길이입니다. 절댓값을 사용해야 합니다.
	int32 fw = MM::Abs(w);
	int32 fh = MM::Abs(h);

	//f는 판별식, t와 s는 각각 판별식의 변화량입니다.
	int32 f = bDrawFlag ? 2 * fh - fw : 2 * fw - fh;
	int32 t = bDrawFlag ? 2 * fh : 2 * fw;
	int32 s = bDrawFlag ? -2 * fw : -2 * fh;

	int32 curX = startPos.X;
	int32 curY = startPos.Y;

	if (bDrawFlag)
	{
		//완만한 경사일 경우
		while (curX != EndPos.X)
		{
			DrawPixel(ScreenPos(curX, curY), src.Color);

			if (f >= 0)
			{
				//아래로 이동하고, 판별식을 수정
				curY += dy;
				f += s;
			}
		
			//x는 항상 증가
			curX += dx;
			f += t;
		}
	}
	else
	{
		while (curY != EndPos.Y)
		{
			DrawPixel(ScreenPos(curX, curY), src.Color);
		
			if (f >= 0)
			{
				curX += dx;
				f += s;
			}
		
			curY += dy;
			f += t;
		}
	}

	//마지막 점을 그립니다.
	DrawPixel(ScreenPos(curX, curY), src.Color);
}

 

 

삼각형이 확실히 잘 그려지고 속도 또한 향상된 것을 볼 수 있습니다.

 

해당 그래픽 라이브러리에 대해서 조금 설명드리자면

Vertex2D에는 2차원 좌표와 32비트 색상 값이 저장되어 있습니다.

 

선을 그을 때는 정점 2개를 잇는 방법을 사용합니다.

 

이 때, 색상은 두 정점의 색상 값을 보간해주는게 맞으나,

편의상 src의 색상으로 선을 그었습니다.

 

색상 보간도 한 번 추가해봅시다.

 

색 보간

 

색의 보간은 선형 보간을 사용합니다.

 

선형 보간이란 시작점 P0 와 끝점 P1이 주어졌을 때, 사이에 위치한 값을 추정하기 위한 방법 중 하나입니다.

이름 그래도 선형적으로 해당 값을 추정하는 간단한 방법입니다.

 

.

선형 보간식을 사용하면 t값을 조절하여 새로운 y를 얻을 수 있습니다.

 

여기서 우리는 좌표를 이용하는 것이 아니라 색상을 이용하기 때문에

아래와 같은 코드를 사용할 수 있습니다.

 

 

그럼 이를 사용해서 색 보간을 적용한 선 그리기 알고리즘을 알아봅시다.

 

 

그러면 이런 식으로 비율과 step을 계산한 뒤에 

 

그릴때마다 ratio를 조금씩 조절하면서 색상을 보간할 수 있습니다.

 

그런데, 색상 보간을 float로 한다는 것에서 조금 불편한 감이 있습니다.

선을 그리는 것은 매우 빈번하게 일어나는 연산이기 때문에 정수 연산을 사용하면 더욱 성능을 끌어올릴 수 있을 것 같습니다.

 

그러면 조금 최적화해봅시다.

 

대충 이런 식으로 colorStep을 계산하고

 

이런 식으로 연산을 바꿔주면

float 연산은 단 한 번 발생하게 됩니다.

그러면 확인해봅시다.

 

 

프레임 속도가 올라간 것까지는 좋으나..

뭔가 색이 제대로 보관되지 않는 모습을 보입니다.

조금 뚝뚝 끊기는 느낌이 보이죠?

 

아무래도 정수 연산이다보니 오차가 존재해서 그런 것 같습니다.

 

그렇다면 조금 더 정확도를 높이기 위해서 이런 식으로 바꿔봅시다.

 

8비트 짜리 색상값을 32비트까지 늘려서 계산한 다음에 다시 8비트로 만들어 주는 것이죠

그러면 정확도를 조금 높일 수 있습니다.

 

이를 위해서 32비트 색상값이 아닌, 128비트 색상값을 추가해줬습니다.

 

 

이런 식으로 Color32와 Color128을 변환할 수 있는 함수를 지원합니다.

 

이런 식으로 128비트로 확장해서 계산한 다음 32비트로 돌려줍시다.

 

 

최종적인 선그리기 알고리즘이 완성되었습니다.

 

void RenderManager::DrawLine(const Vertex2D& src, const Vertex2D& dst) const
{
	//브레젠험 알고리즘
	ScreenPos startPos = Vector2DToScreenPos(src.Position);
	ScreenPos EndPos = Vector2DToScreenPos(dst.Position);

	int32 w = EndPos.X - startPos.X;
	int32 h = EndPos.Y - startPos.Y;

	//그리고자 하는 직선이 완만한지 급경사인지 판단합니다.
	//true 라면 완만한 경사입니다. 
	bool bDrawFlag = MM::Abs(w) >= MM::Abs(h);

	//x값의 변화량입니다.
	//w가 양수라면 양의 방향으로 뻗습니다.
	int32 dx = (w >= 0) ? 1 : -1;
	int32 dy = (h >= 0) ? 1 : -1;

	//판별식에 사용되는 w와 h는 길이입니다. 절댓값을 사용해야 합니다.
	int32 fw = MM::Abs(w);
	int32 fh = MM::Abs(h);

	//f는 판별식, t와 s는 각각 판별식의 변화량입니다.
	int32 f = bDrawFlag ? 2 * fh - fw : 2 * fw - fh;
	int32 t = bDrawFlag ? 2 * fh : 2 * fw;
	int32 s = bDrawFlag ? -2 * fw : -2 * fh;


	//색 보간 코드
	int32 curX = startPos.X;
	int32 curY = startPos.Y;

	Color32 srcColor = src.Color;
	Color32 dstColor = dst.Color;

	int32 length = bDrawFlag ? fw : fh;

	Color128 curColor = srcColor.ToColor128();
	Color128 step = (dstColor.ToColor128() - srcColor.ToColor128()) / length;

	if (bDrawFlag)
	{
		//완만한 경사일 경우
		while (curX != EndPos.X)
		{
			DrawPixel(ScreenPos(curX, curY),curColor.ToColor32());
			curColor = curColor + step;

			if (f >= 0)
			{
				//아래로 이동하고, 판별식을 수정
				curY += dy;
				f += s;
			}
		
			//x는 항상 증가
			curX += dx;
			f += t;
		}
	}
	else
	{
		while (curY != EndPos.Y)
		{
			DrawPixel(ScreenPos(curX, curY), curColor.ToColor32());
			curColor = curColor + step;

			if (f >= 0)
			{
				curX += dx;
				f += s;
			}
		
			curY += dy;
			f += t;
		}
	}

	//마지막 점을 그립니다.
	DrawPixel(ScreenPos(curX, curY), curColor.ToColor32());
}

 

만약 색 보간이 필요없다면 위 코드보단 WinGDI의 LineTo 함수를 쓰는 것이 훨씬 효율적입니다.

그러므로 GDI로 선을 긋는 코드는 다음과 같이 짤 수 있고

 

이런 식으로 분기처리하여 효율적으로 처리할 수 있습니다.

 

역시 하드웨어 가속을 사용해서 그런지 압도적인 성능입니다.

 

코헨-서더랜드 클리핑 알고리즘

 

브레젠험 알고리즘은 시작 지점부터 종료 지점까지 한 칸 한 칸 전진하면서 점을 찍습니다.

만약 매우 긴 선분이 들어왔다면 브레젠험 알고리즘은 의미없는 선을 그리기위한 무의미한 반복을 수행합니다.

 

예를 들어, 800 픽셀의 화면에 20000 픽셀의 선이 들어왔다면, 19200 픽셀만큼 무의미한 픽셀을 찍는 것이죠.

 

그래서 유효한 선분만 걸러내서 그리는 작업이 필요합니다.

이러한 작업을 클리핑 이라고 부릅니다.

 

클리핑 알고리즘은 굉장히 많지만, 코헨-서더랜드 라인 클리핑 알고리즘을 이용해서 구현해보겠습니다. 

해당 방법은 간단하면서 매우 빠릅니다.

 

먼저 화면의 영역을 총 9개로 나눕니다.

그리고 각각의 화면에 비트를 설정합니다.

그리고 각각의 화면에 비트를 설정해줍니다.

 

상은 1000

하는 0100

우는 0010

좌는 0001

로 하여, 상하좌우 비트를 설정하고

 

좌상, 우상, 좌하, 우하 영역은 상하좌우 비트를 조합하여 사용합니다.

그 다음 가운데 영역은 화면 영역으로 0000 비트를 설정합니다.

 

그럼 여기서 존재하는 선의 경우의 수는 3가지 입니다.

1. 선이 뷰를 가로지르는 경우

2. 선이 뷰 내부에 위치한 경우

3. 선이 뷰 외부에 존재할 경우

 

이 경우 선의 시작점과 끝점이 존재하는 영역의 비트값을 비교해서 판달할 수 있습니다.

만약, 두 점의 and 연산의 값이 0이 아니라면, 선이 완전히 밖에 위치한다고 생각할 수 있습니다.

 

먼저 어떤 벡터가 주어질 때, 영역을 얻어내는 함수를 만들어봅시다.

 

그러면 이를 이용해서 클리핑 알고리즘을 한 줄 한 줄 적어봅시다.

 

만약, 시작점과 끝점의 영역 테스트 결과를 and 연산했을 때, 그 값이 0이 아니라면

선이 외부에 존재하는 것이므로 선 그리기를 스킵합니다.

 

만약, 두 점의 테스트 결과가 둘 다 0000이라면 선은 무조건 화면 내부에 존재합니다.

그러므로 true를 리턴하도록 합시다.

 

 

위 그림처럼 두 점이 대각선 반대 방향에 위치한다면, 두 점의 테스트 값을 and 연산이 0이 나옵니다.

이런 선은 클리핑이 필요합니다.

 

클리핑을 하는 방법은 다음과 같습니다.

 

1. 둘 중에 0000 이 아닌 점을 고른다. 만약 둘 다 0000일 경우 임의로 고른다.

2. 선택한 점을 화면과 직선이 접하는 점으로 바꾼다. (직선의 방정식을 활용)

3. 다시 조건식을 수행한다.

 

리턴될 때까지 코드를 반복한다.

 

클리핑을 통해서, 두 점 사이의 관계를 선이 뷰 완전 외부에 위치하는 경우와 선이 뷰 완전 내부에 위치하는 경우

이 2가지로 좁힐 수 있습니다.

 

이를 코드로 표현하면 다음과 같습니다.

 

inline bool RenderManager::CohenSutherlandClip(OUT Vector2D& outWorldVectorSrc, OUT Vector2D& outWorldVectorDst)
{
	int32 srcTest = TestRegion(outWorldVectorSrc);
	int32 dstTest = TestRegion(outWorldVectorDst);

	Vector2D minPos = { -m_worldOrigin2D.X,-m_worldOrigin2D.Y };
	Vector2D maxPos = { m_worldOrigin2D.X, m_worldOrigin2D.Y };

	float w = outWorldVectorDst.X - outWorldVectorSrc.X;
	float h = outWorldVectorDst.Y - outWorldVectorSrc.Y;

	while (true)
	{

		if ((srcTest == 0) && (dstTest == 0))
		{
			return true;
		}
		else if (srcTest & dstTest)
		{
			return false;
		}
		else
		{
			bool isSrc = (srcTest != 0); //test값이 0이 아닌 점 선택
			int testBit = isSrc ? srcTest : dstTest;

			Vector2D clipedVecotor = Vector2D::s_zeroVector;

			//새로운 좌표 선택
			if (testBit < 0b0100)
			{
				//X값 선택
				if (testBit & 0b0001)
				{
					clipedVecotor.X = minPos.X;
				}
				else
				{
					clipedVecotor.X = maxPos.X;
				}

				//x축과 평행한 직선인 경우 
				if (MM::Abs(h) <= MM::ERROR_BOUND)
				{
					clipedVecotor.Y = outWorldVectorSrc.Y;
				}
				else
				{
					//아닐 경우 직선의 방정식을 활용
					clipedVecotor.Y = outWorldVectorSrc.Y + h * (clipedVecotor.X - outWorldVectorSrc.X) / w;
				}
			}
			else
			{
				//Y값 선택
				if (testBit & 0b0100)
				{
					clipedVecotor.Y = minPos.Y;
				}
				else
				{
					clipedVecotor.Y = maxPos.Y;
				}

				//Y축과 평행한 직선인 경우 
				if (MM::Abs(h) <= MM::ERROR_BOUND)
				{
					clipedVecotor.X = outWorldVectorSrc.X;
				}
				else
				{
					//아닐 경우 직선의 방정식을 활용
					clipedVecotor.X = outWorldVectorSrc.X + w * (clipedVecotor.Y - outWorldVectorSrc.Y) / h;
				}
			}

			if (isSrc)
			{
				outWorldVectorSrc = clipedVecotor;
				srcTest = TestRegion(outWorldVectorSrc);
			}
			else
			{
				outWorldVectorDst = clipedVecotor;
				dstTest = TestRegion(outWorldVectorDst);
			}
		}
	}
}

 

while 루프를 돌면서 선은 반복적으로 클리핑되고

결국 조건문에 걸려서 클리핑되게 됩니다.

이를 직선을 그리는 함수에 넣어주면 효율적인 선그리기 알고리즘이 완성됩니다.

 

최종본

 

클리핑 알고리즘을 수행하지 않았을 경우

 

 

클리핑 알고리즘을 수행했을 경우

 

성능이 21%정도 향상되었습니다.