게임 수학 6장 : 아핀공간: 움직이는 가상 세계의 구축

앞서 글에서 말했듯이 벡터의 이동은 같은 차원 내에서는 할 수 없다. 그래서 전단변환을 응용하여 물체의 이동을 구현하려고 사용하게 된 것이 Affine 변환이다. 

개념적으로 이동을 표현하려 하는 물체보다 상위 차원을 사용하여 상위차원의 원점을 기준으로 물체의 차원에 해당하는 점들을 전단변환 한 것이다. 이것을 변환 행렬을 통하여 연산하고, 변환 행렬은 다음과 같이 표현된다.

아핀공간에서 점과 점을 더하면 차원 상수가 1이라는 것을 보장할 수가 없어진다

수식으로 표현하면 P1(x1, y1, 1) + P2(x2, y2, 1) = P3(x1 + x2, y1 + y2, 2)라는 3차원 좌표가 변경되어버린다는 문제가 생긴다. 그렇기 때문에 특정 스칼라 (a, b)를 곱하여 점과 점을 더한다면 차원수를 1로 유지할 수 있는 변환을 할 수 있게 되고 이것을 아핀 결합이라 부른다. 

이것은 이전 글에서 보여줬듯이 삼각함수의 항등공식을 통해 알 수 있다. 

선그리기 알고리즘

현실에서의 선은 연속된 점들의 집합이다. 그런데 가상 공간에서는 선 또한 개별 점들의 집합으로 표현하되 이진숫자로 표현해야 한다. 이 가상곤간에서의 좌표계를 스크린 좌표계라 부른다. 그렇기 때문에 스크린 좌표계에 선을 그릴때에는 계단 현상이 생기는 것은 필연적이고 이것을 최소화 하기 위한 것이 선그리기 알고리즘이다.

대표적으로 직선의 방정식의 기울기를 통해 화면에 선분을 그리는 방식을 채택하는 브레젠헴 알고리즘이 있다.

브레젠험 알고리즘은 시작 위치부터 끝 위치까지 점을 한칸씩 이동한 뒤 판별식을 통해 어떤 위치에 선을 그릴지 계산하고 그리는 알고리즘이다. 

브레젠헴 알고리즘(Bresenham's Algorithm)

브레젠헴 알고리즘은 시작점에서 끝점까지 한 픽셀 단위로 이동하면서, 판별식을 통해 어느 위치에 점을 찍을지 결정하는 알고리즘이다.

(1) 알고리즘 개요

• 정수 연산을 활용하여 빠르게 선을 그릴 수 있다.
• 기울기(Slope)를 직접 계산하는 대신, 누적 오차를 이용하여 선을 생성한다.
• 픽셀 간의 거리를 최소화하며 최적의 위치에 점을 배치한다.

(2) 알고리즘 절차

1. 시작 위치에서 한 픽셀씩 이동한다.
2. 판별식을 사용하여 다음 픽셀을 결정한다.
3. X 좌표를 1 증가시키면서 Y 좌표를 조정한다.
4. 전체적인 선의 기울기에 따라 Y를 조절하여 직선을 유지한다.

(3) 장단점

✅ 장점

• 연산 속도가 빠르다 (부동소수점 연산 없이 정수 연산만 사용)
• 최적의 위치에 점을 배치하여 픽셀 간의 거리 최소화

❌ 단점

• 계단 현상이 심하게 발생 (Anti-aliasing 기법이 필요)
• 정수 연산이지만 특정 경우에는 부정확한 점 선택이 발생할 수 있음

정확한 판별식을 사용한 것은 아니지만 직감적으로 그렸을 때 화면에 선을 그릴때는 다음과 같은 절차를 거쳐 렌더링한다.

브레젠헴 알고리즘은 정수 오차를 통해 판별식으로 직선을 그리고 있다. 때문에 연산 속도가 매우 빠르고, 렌더링 할때 쉽게 그릴 수 있지만, 계단 현상이 심하게 나타날 수 있다는 단점이 있다. 

라인 클리핑 알고리즘(Line Clipping Algorithm)

단순히 직선을 그리는 것뿐만 아니라, 최적화를 위해 그려야 할 부분과 그리지 않아야 할 부분을 구분하는 과정이 필요하다. 이를 해결하는 방법이 라인 클리핑(Line Clipping) 알고리즘이다.

화면을 넘어서는 선을 처리하는 경우는 다음과 같이 구분된다:

1. 완전히 화면 안에 있는 경우 → 그대로 그린다.
2. 완전히 화면 밖에 있는 경우 → 그리지 않는다.
3. 화면을 가로질러 일부만 보이는 경우 → 클리핑을 수행하여 필요한 부분만 그린다.

다음과 같은 상황이 라인 클리핑이 필요한 상황이다.

대표적인 라인 클리핑 알고리즘

• Cohen-Sutherland 알고리즘
  • 사각형 경계 밖의 점을 빠르게 판별하여 선을 잘라내는 방식
• Liang-Barsky 알고리즘
  • 매개변수 형태의 표현을 사용하여 빠르게 선을 자르는 방식
• Nicholl-Lee-Nicholl 알고리즘
  • 특정 방향성을 고려하여 최적화된 방식으로 클리핑 수행

라인 클리핑 알고리즘을 활용하면 불필요한 선을 렌더링하는 연산을 줄일 수 있으며, 이는 비트 연산을 활용한 레이어 마스킹 기법 등으로 확장될 수 있다.

모든 예제 코드의 소스파일은 

GitHub - onlybooks/gamemath: <이득우의 게임 수학> 공식 깃허브 페이지

GitHub - onlybooks/gamemath: <이득우의 게임 수학> 공식 깃허브 페이지

또한 제 개인 깃허브 레포지토리 에 있습니다.

Workspace/C++/GameMath at main · cyphen156/Workspace · GitHub

Workspace/C++/GameMath at main · cyphen156/Workspace

※ 이득우 교수님의 인프런 게임수학강의를 참고하여 작성되었습니다.