[게임수학] 어파인 공간(Affine space)

어파인 공간?

• 벡터공간에서는 벡터가 어디에 위치해 있던지 크기와 방향만 같다면 모두 같은 벡터로 취급한다.
  • 따라서, 벡터 공간에서는 위의 여러 벡터가 엄연히 다른 벡터임에도 불구하고 같은 벡터로 취급될 것이다.
  • 결국 벡터 공간에서는 위치를 중시하는 기하학을 표현하기에 무리가 있다.
• 이를 극복하고자 고안된 것이 바로 어파인 공간이다.
• 어파인 공간에서는 벡터에 위치표현을 위한 점을 추가하여 해당 벡터의 크기, 방향 뿐만 아니라 위치까지도 표현할 수 있게 된다.
  • 벡터공간 + 위치
• 이동이 가능한 부분 공간을 어파인 공간(Affine space)이라고 부른다.

어파인 공간에서의 이동 변환

• 임의의 벡터 (x,y)를 지정한 크기(a,b)만큼 이동시키는 기능은 행렬의 덧셈으로 구할 수 있다.

 ┌ x ┐ + ┌ a ┐ = ┌ x + a ┐
 └ y ┘   └ b ┘   └ y + b ┘

• 다음 행렬 곱을 만족하는 정방행렬 A는 존재하지 않는다.

 A · ┌ x ┐ = ┌ x + a ┐
     └ y ┘   └ y + b ┘

• 그 이유는 표준기저벡터의 원점을 이동시키는 변환이 행렬이 되기 위해선 선형성을 만족해야함
  • 선형성이 되기 위해선 기저벡터는 원점에서부터 출발해야 한다는 조건을 만족해야 함

• 공간의 차원을 하나 더 늘린다면 이를 구현하는 것이 가능하다.
  • 물체를 표현하는데 두 개의 차원을 사용하고, 차원 하나를 더 추가해 선형 변환을 위한 원점과의 연결고리로 활용한다면 선형 변환의 형태로 이동을 구현할 수 있다.

• 이를 구현하기 위해선 전단 변환을 이용해야한다.
  • 전단 변환은 위 그림처럼 표준기저벡터 e1을 고정시킨 상태에서 옆으로 밀어 공간을 기울이는 특징을 지닌다.
  • 위 그림은 2차원에서 전단 변환의 변화를 나타낸 그림이다.
  • (a)는 x축으로 1만큼 밀었을 때 공간의 변화를 나타내고, (b)는 x축으로 2만큼 밀었을 때 변화를 나타낸다.

• 전단 변환으로 변환된 공간의 상단 영역은 위 그림에서 전단 변환을 적용하기 전의 공간 (a)에서 y값이 1인 영역을 살펴보먼 x 범위는 [0, 1]임을 볼 수 있다.
  • 여기서 x축으로 1만큼 민 전단 변환 (b)의 x범위는 [0, 1]에서 1만큼 늘어난 [1, 2]가 된다.
  • 2만큼 민 전단변환 (c)의 x범위는 [0, 1]에서 2만큼 늘어난 [2, 3]이 됨을 확인할 수 있다.
  • 이는 전단 변환을 사용해 공간을 오른쪽으로 밀었을 때 y값이 1인 영역의 x범위는 밀어낸만큼 이동한다는 것을 의미한다.

• 전단 변환의 성질을 활용한다면, 선형 변환의 체계에서 특정 조건하에 이동 기능의 구현이 가능하다.
  • 벡터 y 값에 1을 고정한 상태에서 전단 변환을 적용시키면 다음과 같다

┌ 1 a ┐ · ┌ x ┐ = ┌ x + a ┐
└ 0 1 ┘   └ 1 ┘   └   1   ┘

• 위 수식으로 y = 1이라는 조건하에 a만큼 미는 전단 변환의 결과는 1차원의 이동 변환 x + a로 활용할 수 있다.
  • 이 원리를 2차원 평면에도 적용할 수 있다.
  • 2차원 공간을 한 차원 늘려 3차원 공간으로 확장한 후, 마지막 차원 z 값을 1로 조건을 고정한 전단 변환을 설계

┌ 1 0 a ┐   ┌ x ┐   ┌ x + a ┐
│ 0 1 b │ · │ y │ = │ y + b │
└ 0 0 1 ┘   └ 1 ┘   └   1   ┘

• 마지막 차원의 값이 1이라는 특정 조건을 가지는 전단 변환을 활용하면 게임 콘텐츠 제작에 필수적인 이동 기능을 행렬로 구현할 수 있다.
  • 이를 이동 변환행렬(Translate transformation matrix)이라고 하며 아래와 같이 설계할 수 있다.

//이동 변환행렬(Translate transformation matrix)
    ┌ 1 0 a ┐
T = │ 0 1 b │
    └ 0 0 1 ┘

• 벡터 공간에서 이동을 위해 마지막 차원의 값을 1로 한정한 부분 공간을 Affine space라고 부른다.
  • 한 차원을 높여 설계한 선형 변환을 affine 변환 이라고 한다.

• 3차원의 크기 변환행렬 S와 회전 변환행렬 R은 다음과 같다

    ┌ a 0 0 ┐
S = │ 0 b 0 │
    └ 0 0 1 ┘

    ┌ cosθ -sinθ 0 ┐
R = │ sinθ  cosθ 0 │
    └  0     0   1 ┘

• 위에서 나열은 크기, 회전, 이동 변환은 앞으로 가상 공간의 변환을 다루는데 있어 핵심적으로 사용될 대표적인 어파인 변환이다.
  • 임의의 벡터 (x, y, 1)을 어파인 변환 행렬에 곱한 결과는 아래와 같다.
  • 아래 결과 역시 마지막 차원 값이 1이되어 해당 연산은 어파인 공간에 닫혀 있음을 알수 있다.

┌ a 0 0 ┐   ┌ x ┐  ┌ ax ┐
│ 0 b 0 │ · │ y │ =│ by │
└ 0 0 1 ┘   └ 1 ┘  └  1 ┘

┌ cosθ -sinθ 0 ┐   ┌ x ┐   ┌ cosθx - sinθy ┐
│ sinθ  cosθ 0 │ · │ y │ = │ sinθx + cosθy │
└  0     0   1 ┘   └ z ┘   └       1       ┘

┌ 1 0 a ┐   ┌ x ┐  ┌ x + a ┐
│ 0 1 b │ · │ y │ =│ y + b │
└ 0 0 1 ┘   └ 1 ┘  └   1   ┘

어파인 공간의 마지막 차원의 값이 1인 이유

• 3차원 공간을 이동시켰을 때 이동시킨만큼 이동한 평면의 마지막 차원의 값이 1이기 때문
• 마지막 차원의 값으로 다른 값을 가지는 평면은 이동시킨만큼 이동한 효과를 가지지 않는다.
• 이동하는 양에 대한 것을 표현하는 별도의 공간이 필요
  • 그 공간의 마지막 차원의 값은 0이 될 것
• 마지막 차원의 값이 0과 1로 고정되어 있기 때문에 점에 벡터를 더하여도 그 점은 항상 평행하게 이동할 것

점 + 벡터 = 점
1 + 0 = 1

• 점 + 벡터 = 점을 보장받을 수 있다.

점 - 점 = 벡터
1 - 1 = 0

벡터 + 벡터 = 벡터
0 + 0 = 0

어파인 공간 구성 요소

• 가상 공간의 이동 기능을 어파인 변환으로 구현되어야 할 경우
  • 어파인 공간의 정의에 따라 물체의 마지막 차원 값은 언제나 1이 되어야 한다.

점

• 마지막 차원 값이 1인 어파인 공간의 원소를 점(point)이라고 부른다.
  • 점은 행렬 곱을 사용해 이동이 가능하다.
  • 가상 공간이 이동하려면 물체는 점으로 구성되어야 한다.
• 2차원 공간에서 점은 항상 (x,y,1) 형태여야 한다.
• 3차원 공간의 점이라면 (x,y,z,1) 형태를 띤다.
• 벡터와 점을 구분하기 위해 동차 좌표(Homogeneous Coordinates)를 사용
  • 원래 데이터의 차원을 한차원 높여 줌으로써 점과 벡터를 구분
  • 2차원의 데이터 V = (V1, V2)가 있다면, 이 데이터의 동차 좌표는 V' = (V1, V2, p)가 되며, p가 0이면 벡터를, p가 0이 아니면 점을 의미

이동 벡터

• 행렬 곱의 장점을 살리기 위해 의도적으로 벡터 공간의 부분 공간인 어파인 공간을 사용한다.
  
  • 벡터의 합 연산으로 어파인 공간의 원소인 점을 이동시켰을 때, 행렬 곱의 장점을 유지하기 위해선 그 결과는 항상 어파인 공간에 딛혀 있어야 한다.
  • 이를 위해 어파인 공간은 vector라는 개념을 추가로 제공한다.
• 벡터는 어파인 공간 내의 이동을 지정하기 위해 사용된다.
• 벡터 공간의 원소로 정한 벡터와 구분하기 위해 이동 벡터 또는 변위 벡터(Displacement vector)라고 부른다.

• 이동 벡터는 위 그림과 같이 어파인 공간의 점과 점 간의 최단 거리로 정의된다.
• 어파인 공간의 점 P1에 이동벡터 v를 더한 결과는 P2에 대응되는데 이 수식을 이항하면 이동 벡터를 구할수 있다.

1. 점 P1에 이동 벡터 v를 더한 결과는 어파인 공간의 다른 점 P2에 대응
 P1 + v = P2
 
2. 위 수식에서 P1을 우변으로 이항하면 점과 점의 뺄셈을 통해 이동벡터를 만들 수 있음
 v = P2 - P1
 
3. 여기서 벡터 v는 P1에서 P2로 향하는 벡터를 의미
   (주의)벡터의 뺼셈은 교환법칙이 성립하지 않기 때문에 두 점의 위치를 바꾸면 벡터의 방향이 바뀜
 P1 - P2 = -v

• 점 P1의 좌표를 (x1, y1, 1)로 P2의 좌표를 (x2, y2 ,1)로 지정 했을 때 두 점을 빼서 만든 이동 벡터의 마지막 차원 값은 항상 0이 된다.
  • 이러한 이동 벡터들이 모이면 마지막 차원 z의 값이 항상 0인 영역이 형성될 것

성질

• 아핀 공간의 중심을 원점 O라고 한다면 O는 (0,0,1)이 된다.
• 임의의 점 P의 값을(x,y,1)로 지정한다면 원점 O에서 점 P로 향하는 이동벡터 v는 아래와 같다.

v = P - O = (x,y,1) - (0,0,1) = (x,y,0)

• 위 식을 시각적으로 나타내면 아래와 같다.

• 점과 벡터의 덧셈 연산은 어파인 공간에 대해 닫혀 있다.
  • 마지막 차원을 배제하고 점의 이동을 2차원 평면으로 나타내면, 점과 이동 벡터를 구분하는 마지막 차원을 생략해도 위 그림과 같이 2차원 평면에서 어파인 공간의 점을 점으로, 이동 벡터를 화살표로 표시하면 둘을 구분할 수 있다.
  • 눈에 보이는 물체는 점으로, 물체를 이동시키는데 사용하는 보이지 않는 힘은 화살표로 표현된다.
• 현실 세계 역시 보이는 물체와 보이지 않는 힘으로 구성되어 있다.
  • 어파인 공간의 점과 이동벡터를 사용한다면 현실 세계를 복제한 가상 공간을 구축할 수 있다.
• 물리적인 관점에서 바라본 현실 세계의 3차원 공간을 유클리드 공간(Euclidean space)이라고 한다.
  • 유클리드 공간에서 작용하는 힘을 유클리드 벡터(Euclidean vector)라고 한다.
  • 이에 대응되는 개념이 아핀 공간과 이동 벡터이다.

어파인 결합

• 2차원 평면상의 임의의 두 점 P1(x1, y1, 1)과 P2(x2, y2, 1)에 각각 스칼라 a,b를 곱한 선형 결합의 식은 아래와 같다.

a · P1 + b · P2 = (ax1 + ax2, ay1 + by2, a + b)

• 위 식에서 두 점의 선형 결합 결과가 언제나 점이 되려면 마지막 차원 값 a + b가 1이 되어야 한다.
• x,y 값과 무관하게 a + b = 1의 조건을 유지한다면 점과 점을 결합해 새로운 점을 만들 수 있다.
  • 동일한 원리로 세 점에 대해서도 아래 수식과 같이 모든 스칼라 a, b, c의 합이 1이면 점의 생성이 가능하다.

a · P1 + b · P2 + c · P3 = P4

• 이렇게 여러 개의 점을 결합해 새로운 점을 생성하는 수식을 어파인 결합(Affine combination)이라고 한다.
  •  

두 점의 결합

• 두 점을 어파인 결합해 새로운 점을 생성할 때 어파인 결합이 성립하려면 점에 곱한 두 스칼라의 합이 1이 되어야한다.
  • 이를 바탕으로 a + b = 1 식의 b를 1 - a로 치환하면 계수 a에 대한 식을 얻을 수 있다.
  • 이 식은 언제나 점의 생성을 보장한다.

a · P1 + (1 - a) · P2 = P`

• 스칼라 a 값의 변화에 따라 점의 생성은 달라진다.

1 · P1 + 0 · (x2, y2, 1) = P1       //a에 1을 대입하여 P1을 생성

0 · (x1, y1, 1) + P2 = P2           //a에 0을 대입하여 P2를 생성

1/2 · (x1, y1, 1)  + 1/2 · (x2, y2, 1) = ((x1 + x2) / 2,  (y1 + y2) / 2, 1) 
//a에 0.5를 대입하여 중점을 생성

• 두 점 P1과 P2의 어파인 결합을 통해 새로운 점을 생성하면, a 값이 양의 방향으로 커질수록 P1의 바깥쪽 방향에 점이 생성된다.
  • a 값이 음의 방향으로 커질수록 P2의 바깥쪽 방향에 점이 생성된다.
  • 어파인 결합으로 생성되는 점을 모두 모으면 두 점 P1과 P2를 지나는 무한한 긴 선이 만들어질 것
• a의 범위가 좌우로 무한하면 직선(Line), 한쪽으로만 무한하면 반직선(Ray), 양쪽다 유한하면 선분(Line segment)라고 부른다.

• 반직선은 게임 제작에서 전방에 물체가 있는지 탐지하기 위해 사용하는 기능인 레이캐스팅(Raycasting)에 이용된다.
  • 지정한 위치에 특정 방향으로 반직선을 던져 이와 맞닿은 물체를 탐지하는 기능
• 컴퓨터 그래픽스에서 각광받은 레이트레이싱(Raytracing)도 반직선 개념이 사용된다.
  • 화면에 도달한 빛의 경로를 거꾸로 추적해 현실 세계와 유사하게 빛의 경로를 시뮬레이션해 사실적인 이미지를 만들어내는 기법
• 선분은 시작점과 끝점의 위치가 정해저 있는 선을 말한다.
  • 프로그래밍을 활용해 화면에 선을 그리려면 무한이라는 추상적인 개념을 배제하고 명확하게 시작점과 끝점을 정해주어 선분의 형태로 정보가 제공되어야 한다.

선 그리기 알고리즘

벡터를 모니터 점으로 표현

• 수학에서 벡터를 표현할 때에는 y축이 위쪽을 향하는 데카르트 좌표계를 사용한다.
  • 하지만 모니터 화면의 좌표계는 y축이 아래쪽을 향하는 방식을 사용한다.
  • 이를 스크린 좌표계(Screen coordinate system)라고 한다.

• 스크린 좌표계는 실수가 아닌 정수를 사용한다.
  • 데카르트 좌표계는 빈틈이 없는 연속된(Continuous)실수로 평면을 채우지만, 스크린 좌표계는 서로 독립된 영역을 가지는 이산적인(Discrete) 정수를 사용한다.
  • 그래서 하나의 스크린 좌표는 네모난 영역에 대응된다.
• 스크린 좌표계를 사용해 화면에 무언가를 표현하기 위해서는 반드시 색상이 함께 지정되어야한다.
  • 스크린 좌표와 색상에 대응하는 화면의 구성 요소를 픽셀(Pixel)이라고 한다.
• 벡터를 화면의 점으로 최종 표현하기 위해서는 실수로 표현된 벡터 좌표를 정수로 변환한 후 색상을 부여하는 과정을 거쳐야 한다.
  • 이러한 변환 과정을 픽셀화(Rasterization)라고 한다.

알고리즘 구현

• 직선의 방적식을 활용해 선을 그리기 위해선 주어진 두 점에서 스칼라 a값의 범위를 0부터 1까지 조금씩 늘려나가면서 벡터를 생성해야함
  • 이후 벡터에 대응하는 픽셀을 하나씩 찍어야한다.
• 위 방식은 응용적인 측면에서 효과적이지 않다.
  • 점을 찍을 모니터 화면은 정수 좌표로 구성되어 있기 때문에 하나의 픽셀에 대응되는 다수의 벡터가 생성될 것이다.
• 정수만 사용해 효율적으로 화면에 선분을 그리는 브레젠험 알고리즘(Bresenham's algorithm)이 있다.
  • 중점 알고리즘(Midpoint algorithm)이라고도 한다.

• 위 그림과 같이 8등분 영역으로 구분한 후 각 영역별로 그려내는 방식을 사용함
  • 브레젠험 알고리즘은 y축이 아래로 증가하는 스크린 좌표계에서 구현되므로 회전 방향은 시계 방향이 된다.
• 첫 번째 영역인 1팔분면에 대해 살펴본다면
  • 1팔분면은 [0도, 45도]의 범위를 가진다.
  • 해당 영역에 존재하는 모든 선의 기울기가 1을 넘어설 수 없음을 의미함
  • 1팔분면에 위치한 선을 구성하는 점의 진행은 아래 그림과 같이 평행하거나 한 칸만 내려가는 특징이 있다.

• 1팔분면에 브레젠험 알고리즘을 구현하는 수식
  • 정수로 변환된 두 점의 스크린 좌표가 주어질 때 첫 번째 시작점의 정수 좌표를 (x0, y0)로 표시하고 선분의 너비와 높이를 구한 후 각각 정수 w와 h로 지정
  • 아래 그림은 이를 시각화한 것

• 시작 위치의 픽셀 (x0, y0)을 찍은 후 오른쪽 칸의 픽셀을 어디 찍을 것인가
  • 다음 픽셀의 x좌표는 x0 + 1로 구할 수 있다.
  • 오른쪽으로 한 칸 이동한 좌표의 y값은 1팔분면의 특성상 y0아니면 y0 + 1 두가지 경우만 존재함
  • 이 중에서 하나를 선택하기 위해 중간 값 0.5를 사용하는 것이 브레젠험 알고리즘의 기본 원리
  • x좌표 x0 + 1에서 그릴 선이 y0 + 0.5보다 위에 있는지 아래에 있는지 판별해야함
  • 이를 위해 직선의 방정식을 사용 (기울기 a 값은 h/w로 구할 수 있음)

y0 = (h/w)x0 + b
y = (h/w)x + y0 - (h/w)x0

(h/w)x + y0 - (h/w)x0 < y0 + 0.5
        hx + wy0 -hx0 < wy0 + 0.5w
     h(x - x0) - 0.5w < 0
       2h(x - x0) - w < 0
  2h(x0 + 1 - x0) - w < 0
               2h - w < 0

• 높이와 너비만 사용한 수직 2h - w값과 0을 비교하는 것만으로, 다음 픽셀의 위치를 계산할 수 있음

라인 클리핑 알고리즘

• 브레젠험 알고리즘은 단순하고 빠른 알고리즘이지만 이것만으로 선을 그리기에는 충분하지 않다.
  • 시작지점에서 목표지점에 도달할 때까지 한 픽셀식 전진하면서 점을 찍기 때문에, 화면을 벗어나는 굉장히 큰 값이 들어오더라도 목표에 도달할 때까지 한 칸식 전진하면서 계산해야함
  • 굉장히 긴 선분이 들어와도 화면 영역에 유요한 선분으로 잘라주는 알고리즘이 있다면 이 문제를 예방할 수 있음
• 선분이 가진 성질은 유지하면서 지정된 영역에 맞는 데이터로 재설정하는 작업을 클리핑(Clipping)이라고 한다.
  • 코헨-서덜랜드 라인 클리핑 알고리즘(Cohen-Sutherland line clipping algorithm)을 통해 구현 가능
• 입력된 선분을 그릴 영역을 화면과 그 바깥 영역을 포함해 총 9개로 설정
  • 각 영역마다 상위 두 비트는 상하 정보를, 하위 두 비트는 좌우 정보를 담아 총 네 자리 이진수 값으로 고유한 값을 부여

1001 1000 1010
0001 0000 0010
0101 0100 0110

• 가운데 0000의 영역은 눈에 보이는 화면 영역을 의미한다.
  • 선분을 구성하는 시작점과 끝점이 모두 0000 영역에 있다면 클리핑 없이 선을 그리면 된다.
  • 한 점이라도 0000이 아닌 영역에 위치한다면 클리핑을 해야함
  • 선분이 화면을 지나지 않는다면 그리지 않음 (계산량을 줄이는 데 도움이 된다)
• 시작점과 끝점을 입력 받아서 네 자리 이진수 값으로 계산하고 두 점의 테스트 값을 & 연산하여 0보다 큰값이 나오면 그리기를 건너뛰고 0이나오면 클리핑하여 화면 영역의 점으로 변경해야한다.

 

 

 

 

 

출처

https://m.yes24.com/Goods/Detail/107025224

이득우의 게임 수학 - 예스24

https://wecandev.tistory.com/208

[이득우 게임수학] 6. 아핀공간 : 움직이는 가상 세계의 구축

https://wonjayk.tistory.com/92

어파인 공간 (Affine Space)

https://velog.io/@parksj3205/%EA%B2%8C%EC%9E%84%EC%88%98%ED%95%99%EC%9D%98-%EC%9D%B4%ED%95%B4-%EC%9D%B4%EB%93%9D%EC%9A%B0-%EA%B5%90%EC%88%98%EB%8B%98-%EA%B0%95%EC%9D%98-%EC%A0%95%EB%A6%AC-3.-%EB%AC%BC%EC%B2%B4%EC%9D%98-%EC%88%98%ED%95%99-%EC%A0%95%EC%A0%90%EA%B3%BC-%EC%82%BC%EA%B0%81%ED%98%95

[게임수학의 이해 이득우 교수님 강의 정리] 3. 물체의 수학 Ⅱ : 정점과 삼각형