브레젠험 알고리즘의 구현

- 개요

브레젠험 알고리즘을 사용하여 스크린 좌표계에서 선을 그리는 예제를 분석한다

다음의 예제는 모든 8분면에 대응하는 브레젠험 알고리즘을 구현하였다

• 1분면 : (+x, +y)
• 2분면 : (+x, -y)
• 3분면 : (-x, -y)
• 4분면 : (-y, -x)
• 5분면 : (-y, +x)
• 6분면 : (-x, +y)
• 7분면 : (+x, +y)
• 8분면 : (+y, +x)

 

그릴 픽셀에 대한 판별식

 

브레젠험 알고리즘의 판별식은 위와 같다

판별식의 결과에 따라 그릴 픽셀의 위치를 설정한다

• 판별식의 값이 0보다 작은 경우 : 수평으로 픽셀을 그림
• 그렇지 않은 경우 : 대각선으로 픽셀을 그림

 

- 예제

...

void WindowsRSI::DrawLine(const Vector2& InStartPos, const Vector2& InEndPos, const LinearColor& InColor)
{
	//////////////////////////////////////////////////////////////////////////////////////////
	// 그릴 선의 시작점과 끝점이 화면을 벗어나는 경우, 클리핑 알고리즘을 진행
	Vector2 clippedStart = InStartPos;
	Vector2 clippedEnd = InEndPos;
	Vector2 screenExtend = Vector2(_ScreenSize.X, _ScreenSize.Y) * 0.5f;
	Vector2 minScreen = -screenExtend;
	Vector2 maxScreen = screenExtend;
	if (!CohenSutherlandLineClip(clippedStart, clippedEnd, minScreen, maxScreen))
	{
		return;
	}
	//////////////////////////////////////////////////////////////////////////////////////////

	// 선의 시작점과 끝점을 스크린 좌표계로 변환하고 변수에 저장
	ScreenPoint startPosition = ScreenPoint::ToScreenCoordinate(_ScreenSize, clippedStart);
	ScreenPoint endPosition = ScreenPoint::ToScreenCoordinate(_ScreenSize, clippedEnd);

	// 스크린의 너비와 높이를 변수에 저장
	int width = endPosition.X - startPosition.X;
	int height = endPosition.Y - startPosition.Y;

	// 직선의 기울기를 판단하는 isGradualSlope 변수의 값을 설정
	// x축의 진행 방향과 y축의 진행 방향이 양수인지 / 음수인지 판단하고 변수에 저장 
	bool isGradualSlope = (Math::Abs(width) >= Math::Abs(height));
	int dx = (width >= 0) ? 1 : -1;
	int dy = (height > 0) ? 1 : -1;
	
	// 판별식에서 사용할 h와 w를 변수에 저장
	int fw = dx * width;
	int fh = dy * height;

	// 브레젠험 알고리즘의 판별식을 설정
	// 순서대로 최초 판별식 / 선이 변화가 없는 경우의 판별식 / 선에 변화가 있는 경우의 판별식
	// 최초로 선을 그릴 픽셀의 x / y 좌표를 변수에 저장
	int f = isGradualSlope ? fh * 2 - fw : 2 * fw - fh;
	int f1 = isGradualSlope ? 2 * fh : 2 * fw;
	int f2 = isGradualSlope ? 2 * (fh - fw) : 2 * (fw - fh);
	int x = startPosition.X;
	int y = startPosition.Y;

	// isGradualSlope가 참이라면, 선에 기울기가 완만하므로 1 / 4 / 5 / 8 분면의 선을 그림
	if (isGradualSlope)
	{
		// 끝점에 도달할때까지 무한 반복
		while (x != endPosition.X)
		{
			SetPixel(ScreenPoint(x, y), InColor);

			// 판별식이 0보다 작으면 선에 변화가 없는 경우의 판별식 사용
			if (f < 0)
			{
				f += f1;
			}
			// 판별식이 0보다 크거나 같으면 선에 변화가 있는 경우의 판별식 사용
			else
			{
				f += f2;
				y += dy; // 해당 상황에서는 y축으로는 한 칸 진행해야 함
			}

			// 다음 픽셀로 이동
			x += dx;
		}
	}
	// isGradualSlope가 거짓이라면, 선에 기울기가 급하므로 2 / 3 / 6 / 7 분면의 선을 그림
	// x와 y의 값을 바꿔 진행
	else
	{
		// 끝점에 도달할때까지 무한 반복
		while (y != endPosition.Y)
		{
			SetPixel(ScreenPoint(x, y), InColor);
			
			// 판별식이 0보다 작으면 선에 변화가 없는 경우의 판별식 사용
			if (f < 0)
			{
				f += f1;
			}
			// 판별식이 0보다 크거나 같으면 선에 변화가 있는 경우의 판별식 사용
			else
			{
				f += f2;
				x += dx; // 해당 상황에서는 x축으로는 한 칸 진행해야 함
			}

			// 다음 픽셀로 이동
			y += dy;
		}
	}
}

...