이번 글은 코헨 서더랜드 알고리즘에 관한 글입니다.
1. 코헨 서더랜드 알고리즘
이 알고리즘은 라인 클리핑에서 사용되는 컴퓨터 그래픽 알고리즘 입니다.
2차원 공간은 아래의 그림처럼 9개의 영역으로 분할 한 다음 볼 수 있는 선의 부분을 효율적으로 연산합니다.
상 = 1000
하 = 0100
좌 = 0001
우 = 0010
이 알고리즘이 선을 클리핑 하는 방식은 다음과 같습니다.
1. 선을 그리는 두 개의 점을 입력 받고 각 점이 위치한 영역을 체크합니다.
2. 위의 체크한 결과에서 두 점이 모두 0000 이 나오면 선은 모두 화면 안에 있으므로 바로 선을 그립니다.
3. 두 점의 검사 결과를 비트연산 &(and)를 통해 0000 이 나오지 않는 다면 해당 선은 화면 바깥에 있으므로 선을 그리지 않습니다.
4. 나머지 경우는 두 점중 하나만 화면안에 있는 경우로 클리핑 작업이 필요합니다.
직선의 기울기 방정식을 이용해 각 점을 계산한 후 최종 선을 그립니다.
예시 그림으로 한번 살펴 봅시다.
(모두 스크린 좌표, 스크린 사이즈는 가로 800 세로 400)
위 그림의 붉은 색 선을 그린다고 가정하고 위의 알고리즘 순서에 따라 가보겠습니다.
1. 각 점이 위치한 영역을 체크합니다. 일단 P1은 스크린 좌표 안에 있으므로 0000이라는 결과 값이 나옵니다. 그리고 P2의 좌표는 (1000, 100) 이므로 그려줄 스크린 최대 넓이를 벗어납니다. 위의 그림을 봤을 때 결과값은 0100 이 나옵니다.
2. 1번에서 체크 했던 결과 두 점 모두가 0000이 아니므로 넘어갑니다.
3. 두 점의 영역 결과를 &(and) 연산 해줍니다.
결과는 0000 이 나와 다음 과정으로 넘어갑니다.
4. 위에서의 기타 과정이 끝나고 라인 클리핑이 필요하다는 것이 결정되었습니다. 이제 실제로 라인 클리핑이 이루어져야합니다.
화면 정 가운데가 원점 (0,0) 이라고 했을때 최소 범위는 (-400, -200) 이고 최대 범위는 (400,200) 입니다.
먼저 직선의 기울기를 구해줍니다.
위의 경우 P2 의 X 좌표가 최대 범위를 넘어가기 때문에 X의 값은 최대 값인 400 입니다.
그럼 P2 Y 값은 P1 X의 값이 400일때의 값을 구해야합니다.
Y의 값을 구하는 것은 두 점의 교점을 구하는 식을 쓰면 간단합니다.
(시작 Y 좌표) + ((높이) * ((변한 X좌표의 값) - (시작 X 죄표))/(넓이))
즉, P2.Y = -100 + (250 * (400-(-40))/640) = 71.875 입니다.
최종적으로 P2의 클리핑된 좌표는 (400, 71.875)로
직선은 (-40,-100) 에서 (400,71.875)의 위치로 그려집니다.
2. 구현
int exeptCount = 0;
// 영역 검사
int startTest = TestRegion(InOutStartPos, InMinPos, InMaxPos);
int endTest = TestRegion(InOutEndPos, InMinPos, InMaxPos);
while (true)
{
// 안전장치
if (exeptCount > 4)
return false;
// 모든 점이 화면 안에 있을때
if ((startTest == 0) && (endTest == 0))
{
return true;
}
else if (startTest & endTest) // 모든 점이 바깥에 있을때
{
return false;
}
Vector2 clipPos;
int currentTest = startTest ? startTest : endTest;
float width = InOutEndPos.X - InOutStartPos.X;
float height = InOutEndPos.Y - InOutStartPos.Y;
// 좌우 검사
if (currentTest < 0b0100)
{
// 왼쪽이면 MinPos.X 가 되고 오른쪽이면 MaxPos.X 가 된다.
clipPos.X = currentTest & 0b0001 ? InMinPos.X : InMaxPos.X;
clipPos.Y = InOutStartPos.Y + height * (clipPos.X - InOutStartPos.X) / width;
}
else // 상하 검사
{
// 위쪽이면 MaxPos.Y가 되고 아래쪽이면 MinPos.Y 가 된다.
clipPos.Y = currentTest & 0b1000 ? InMaxPos.Y : InMinPos.Y;
clipPos.X = InOutStartPos.X + width * (clipPos.Y - InOutStartPos.Y) / height;
}
// 결과 값을 대입
if (currentTest == startTest)
{
InOutStartPos = clipPos;
startTest = TestRegion(InOutStartPos, InMinPos, InMaxPos);
}
else
{
InOutEndPos = clipPos;
endTest = TestRegion(InOutEndPos, InMinPos, InMaxPos);
}
exeptCount++;
}
위에서 예시로 활용했던 좌표로 선 그리기 및 클리핑
회전
(SoftRenderer 는 강의 시간 활용 목적으로 교수님께서 제공 해주신 엔진입니다...)
댓글
댓글 쓰기