라인 클리핑 알고리즘의 구현

- 개요

서덜랜드 - 코헨 라인 클리핑 알고리즘의 영역

 

위와 같이 우리가 바라보는 화면의 영역인 0000을 기준으로 라인 클리핑 알고리즘을 수행한다

이때 클리핑을 하는 상황은 다음과 같이 정리할 수 있다

• 첫 번째 상황 : 화면 안에 선이 위치해서 자를 필요가 없는 경우
• 두 번째 상황 : 화면 밖에 선이 위치해서 그릴 필요가 없는 경우
• 세 번째 상황 : 화면을 가로질러 선이 위치해서 화면에 유효한 영역으로 잘라내야 하는 경우

 

- 선을 구성하는 점의 영역 값을 판단하는 로직

...

int WindowsRSI::TestRegion(const Vector2& InVectorPos, const Vector2& InMinPos, const Vector2& InMaxPos)
{
	int result = 0;

	/*
	* 상위 2개의 비트 : 상하 정보
	* 하위 2개의 비트 : 좌우 정보
	* 1000 = 상
	* 0100 = 하
	* 0010 = 우
	* 0001 = 좌
	*/

	// 인자로 넘겨준 벡터의 X 값이 최솟값보다 작은 경우 : 해당 벡터는 왼쪽에 위치
	// 따라서 좌우 비트를 01로 설정
	if (InVectorPos.X < InMinPos.X)
	{
		result = result | 0b0001;
	}
	// 인자로 넘겨준 벡터의 X 값이 최댓값보다 큰 경우 : 해당 벡터는 오른쪽에 위치
	// 따라서 좌우 비트를 10으로 설정
	else if (InVectorPos.X > InMaxPos.X)
	{
		result = result | 0b0010;
	}

	// 인자로 넘겨준 벡터의 Y 값이 최솟값보다 작은 경우 : 해당 벡터는 아래쪽에 위치
	// 따라서 상하 비트를 01로 설정
	if (InVectorPos.Y < InMinPos.Y)
	{
		result = result | 0b0100;
	}
	// 인자로 넘겨준 벡터의 Y 값이 최댓값보다 큰 경우 : 해당 벡터는 위쪽에 위치
	// 따라서 상하 비트를 10으로 설정
	else if (InVectorPos.Y > InMaxPos.Y)
	{
		result = result | 0b1000;
	}

	return result;
}

...

 

위와 같이 4개의 비트로 구성된 이진수를 사용하여 해당 벡터에 대한 영역값을 설정한다

 

- 코헨 - 서덜랜드 라인 클리핑 알고리즘을 구현한 로직

...

bool WindowsRSI::CohenSutherlandLineClip(Vector2& InOutStartPos, Vector2& InOutEndPos, const Vector2& InMinPos, const Vector2& InMaxPos)
{
	// 선을 구성하는 시작점과 마지막점의 영역을 판단 
	int startTest = TestRegion(InOutStartPos, InMinPos, InMaxPos);
	int endTest = TestRegion(InOutEndPos, InMinPos, InMaxPos);

	// 선의 너비와 높이를 설정
	float width = (InOutEndPos.X - InOutStartPos.X);
	float height = (InOutEndPos.Y - InOutStartPos.Y);

	while (true)
	{
		// 화면 안에 선이 존재하는 경우 -> 클리핑없이 True 반환
		if ((startTest == 0) && (endTest == 0)) 
		{
			return true;
		}
		// 화면 밖에 선이 존재하는 경우 -> 그릴 필요가 없으므로 False 반환
		else if (startTest & endTest) 
		{
			return false;
		}
		// 선이 화면을 지나가는 경우 -> 화면에 유효한 영역으로 클리핑
		else 
		{
			// 클리핑하기 위한 변수
			// 각각 교차점 / 시작점이 화면에 위치했는지 여부 / 현재 검사 중인 점의 영역
			Vector2 clippedPosition;
			bool isStartTest = (startTest != 0);
			int currentTest = isStartTest ? startTest : endTest;

			// currentTest의 비트코드를 확인해 어느 경계와 교차하는지 판별
			// 경계의 비트 : 상(1000) / 하(0100) / 좌(0001) / 우(0010)

			// X축 경계와 교차하는 경우
			if (currentTest < 0b0100)
			{
				// 왼쪽 경계(0001)와 교차하는 경우
				if (currentTest & 1)
				{
					clippedPosition.X = InMinPos.X;
				}
				// 오른쪽 경계(0010)와 교차하는 경우
				else
				{
					clippedPosition.X = InMaxPos.X;
				}
				
				// 수평선인 경우 Y값은 그대로 유지
				if (Math::EqualsInTolerance(height, 0.0f))
				{
					clippedPosition.Y = InOutStartPos.Y;
				}
				// 아닌경우, 직선의 방정식을 사용하여 Y값 갱신
				else
				{
					clippedPosition.Y = InOutStartPos.Y + height * (clippedPosition.X - InOutStartPos.X) / width;
				}
			}
			// Y축 경계와 교차하는 경우
			else
			{
				// 아래 경계(0100)과 교차하는 경우
				if (currentTest & 0b0100)
				{
					clippedPosition.Y = InMinPos.Y;
				}
				// 위 경계(1000)과 교차하는 경우
				else
				{
					clippedPosition.Y = InMaxPos.Y;
				}

				// 수직선인 경우 X는 그대로 유지
				if (Math::EqualsInTolerance(width, 0.0f))
				{
					clippedPosition.X = InOutStartPos.X;
				}
				// 아닌 경우, 직선의 방정식을 사용하여 X값 갱신 
				else
				{
					clippedPosition.X = InOutStartPos.X + width * (clippedPosition.Y - InOutStartPos.Y) / height;
				}
			}

			// 클리핑한 결과로 다시 테스트 진행.
			if (isStartTest)
			{
				InOutStartPos = clippedPosition;
				startTest = TestRegion(InOutStartPos, InMinPos, InMaxPos);
			}
			else
			{
				InOutEndPos = clippedPosition;
				endTest = TestRegion(InOutEndPos, InMinPos, InMaxPos);
			}
		}
	}

	return true;
}

...

 

위와 같이 함수를 구성하여 코헨-서덜랜드 클리핑 알고리즘을 구현하였다

클리핑할 수 있는 3개의 상황을 고려하여 로직을 구성하였다

• 1) 선을 구성하는 시작점과 끝점이 모두 화면에 존재하는 경우 : 두 점 모두 0000의 영역값
• 2) 선을 구성하는 시작점과 끝점이 모두 화면 밖에 존재하는 경우 : 두 점 모두 0000보다 큰 영역값
• 3) 선이 화면을 지나가는 경우
  • 현재 영역값이 X축 경계와 Y축 경계와 교차하는지 판단하여 로직 진행
  • 위의 클리핑된 값으로 다시 테스트를 진행하여 영역값을 클리핑된 값으로 조정

 

- 선 그리기 함수에서 클리핑 알고리즘 사용

...

void WindowsRSI::DrawLine(const Vector2& InStartPos, const Vector2& InEndPos, const LinearColor& InColor)
{
	// 선의 시작점과 끝점 
	Vector2 clippedStart = InStartPos;
	Vector2 clippedEnd = InEndPos;
	
	// 화면의 크기 절반의 값을 screenExtend에 저장
	Vector2 screenExtend = Vector2(_ScreenSize.X, _ScreenSize.Y) * 0.5f;
	
	// screenExtend 값을 사용하여 화면의 최댓값과 최솟값을 설정
	Vector2 minScreen = -screenExtend;
	Vector2 maxScreen = screenExtend;

	// 라인 클리핑 알고리즘을 사용 -> false가 나왔다면 해당 선은 화면의 영역 밖에 위치하므로 그대로 종료
	if (!CohenSutherlandLineClip(clippedStart, clippedEnd, minScreen, maxScreen))
	{
		return;
	}
    
    	...
    
}

...

 

위와 같이 코헨-서덜랜드 직선 클리핑 알고리즘을 선 그리기 함수에서 적용하였다

그릴 선의 시작점과 끝점을 설정한 후에 라인 클리핑 알고리즘을 적용하여 false가 나왔다면 그대로 종료한다