원글 페이지 : 바로가기
어파인 공간? 벡터공간에서는 벡터가 어디에 위치해 있던지 크기와 방향만 같다면 모두 같은 벡터로 취급한다. 따라서, 벡터 공간에서는 위의 여러 벡터가 엄연히 다른 벡터임에도 불구하고 같은 벡터로 취급될 것이다. 결국 벡터 공간에서는 위치를 중시하는 기하학을 표현하기에 무리가 있다. 이를 극복하고자 고안된 것이 바로 어파인 공간이다. 어파인 공간에서는 벡터에 위치표현을 위한 점을 추가하여 해당 벡터의 크기, 방향 뿐만 아니라 위치까지도 표현할 수 있게 된다. 벡터공간 + 위치 이동이 가능한 부분 공간을 어파인 공간(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 39가지 실시간 렌더링 게임 프로그래밍 실습 예제를 하나씩 따라 해보며 독자가 직접 체득하는 흥미로운 게임 수학의 세계! 게임 개발자와 그래픽 아티스트들이 궁금해 했던 3D 가상 세계와 메타 m.yes24.com https://wecandev.tistory.com/208 [이득우 게임수학] 6. 아핀공간 : 움직이는 가상 세계의 구축 이동이 가능한 부분 공간을 아핀 공간(Affine space)이라고 부른다. 6.1 이동 변환을 위한 아핀 공간 임의의 벡터 (x,y)를 지정한 크기(a,b)만큼 이동시키는 기능은 행렬의 덧셈으로 구할 수 있다. ┌ x wecandev.tistory.com https://wonjayk.tistory.com/92 어파인 공간 (Affine Space) 멀티플뷰 지오메트리에서도 나왔었고, BazAR를 하면서도 나왔었지만사실 두리뭉실하게 알고 있는것이 전부였던 어파인 공간. 두리뭉실하니까 좀 더 알아보자 1. 어파인 공간 벡터공간에서는 벡 wonjayk.tistory.com 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. 물체의 수학 Ⅱ : 정점과 삼각형 3차원 공간의 이동 구현을 위해서는 물체를 표현하는 3차원 + 이동을 표현하는 1차원총 4차원의 공간이 필요함4차원 공간을 그림으로 표현할 수가 없음.그래서 2차원 공간의 이동 구현으로 대신 velog.io