회사에서는 1주일마다 주간회의때 주제 하나씩을 잡아서 간략한 설명형식의 세미나를 한다.
지금까지 다뤄왔던 주제는 다음과 같다.
다는 생각이 안나지만, 대략 이러한 종류의 주제들로 약 8개월동안 진행해 왔다. 단순계산으로 24가지 주제를 다뤄온 셈인데, 이제부터라도 기록을 남기기 위해 포스팅을 해 놓아야 겠다는 생각이 든다.
지난주의 주제는 충돌.
충돌계산의 핵심은 매개변수(parametric form) 방정식이다.
좌표평면에서 x절편 A, y절편 B를 가지는 직선의 방정식은 일반적으로 다음과 같이 쓰곤 한다.
y = -(B/A)x + B
이때 A' = -B/A 로 정의하면 간략히 다음과 같이 쓸 수 있다.
y = A'x + B
이와 같은 형태는 표현은 간단하지만, 직선이 y축과 평행한 경우는 절대로 표현이 불가능하다. 따라서, 평면에서 임의의 직선을 표현하는 좀 더 나은 방식은 음함수 형태로, 다음과 같이 쓰는 것이다.
Bx + Ay - AB = 0
이와 같은 형태는 평면상에서 임의의 직선을 표현할 수는 있지만, 특정한 조건을 만족하는 점을 계산하려면 (이를테면, 두 직선의 교점) 여러차례의 이항과 소거를 거쳐야 하는 단점이 있다. 또한 3차원 이상의 공간상에서의 직선은 이와 같은 형태로 표현이 불가능하다는 결점이 있다.
매개변수 방정식에는 위와 같은 결점이 없다. 위의 2차원 평면상의 직선은, 매개변수 t에 대하여, 다음과 같이 쓸 수 있다.
x = -At + A
y = Bt
이는 다시, 벡터 방정식으로 a=(A,0), b=(b,0)으로 정의하면, 직선 l은, 다음 식으로 표현된다.
l = (b-a)t + a
이러한 형태의 표현은 3차원 이상의 공간에서도 일반적으로 성립하며, 표기도 간단하고, 매개변수 t의 범위를 제한함으로써 선분이나 반직선등을 용이하게 표현할 수 있다. 또한 한가지 변수 t만 결정하면 직선상의 한 점을 지정할 수 있으므로, 풀이도 비교적 용이하다. 기본적인 충돌 계산은, 충돌 대상이 되는 도형을 매개변수 형태로 표현하는 것으로 시작한다.
보통 충돌 시스템을 구현할 때에는 간단한 기하도형을 몇가지 정해놓고 시작하는데, 일반적으로 다음과 같은 도형들이 충돌계산에 사용되곤 한다.
대략 9개 정도의 도형이 널리 이용되는데, 이들에 대한 구현을 모두 하려면, 각 도형이 다른 도형, 혹은 같은 도형과 충돌할 수 있으므로, 45 가지 경우를 구현해야 한다. 이에 대한 설명을 모두 하는 것은 길고 시간이 오래걸리므로, 여기에서는 직선-구, 직선-삼각형의 경우만 다룬다.
일반적으로 직선 l은, 직선의 방향벡터 d와 직선위의 한점을 가리키는 위치벡터 p가 주어질 때, 실매개변수 t에 대하여 다음 형태로 쓸 수 있다.
l = dt + p
또한 일반적인 구 s는, 중심 c와 반지름 r만으로 완전하게 정의할 수 있으므로, 구의 방정식은 벡터 형태로 다음과 같이 쓸 수 있다.
|s - c| = r
이와 같은 형태는 계산이 곤란하므로, 내적 형태로 다음과 같이 쓸 수 있다.
(s-c)·(s-c) = r*r
이때, 구 s와 직선 l의 교차점은 s = l 로 놓고 풀어 직선의 매개변수 t를 결정하는 작업이다. 구의 방정식에서 s = l을 대입하고 전개하면, t에 대한 2차방정식을 구할 수 있으므로, 이 2차방정식의 근으로 교점을 결정할 수 있다. 이 방정식이 2개의 실근을 가지면 직선은 구를 관통하며, 1개의 중근을 가지면, 직선은 구와 접하고, 허근을 가지면 직선은 구와 만나지 않는다.
3차원 공간상에서 삼각형과 직선의 충돌은 먼저, 삼각형을 매개변수 형태로 표현하는 것으로 시작한다. 삼각형 ABC에서, 벡터CA를 a, 벡터CB를 b라고하고, 점C의 위치벡터를 c라고 재명명하면, 삼각형 내부의 영역 q는, 두 매개변수 u,v에 대하여 다음과 같이 표현된다.
q = au + bv + c (u >= 0, v >= 0, 0 <= u+v <= 1 )
여기서 삼각형과 직선의 교점을 구하는 것은, 직선 l이 주어졌을 때, q = l로 놓고 풀어 직선의 매개변수 t와 삼각형의 매개변수 u,v를 구하는 문제로 바뀐다. l을 대입하면, 풀어야할 방정식이 나온다.
dt + p = au + bv + c
매개변수에 대한 항을 이항하면, 다음과 같다.
dt - au -bv = c-p
표현을 간단히 하기 위해 a' = -a, b' = -b, o = c-p 로 치환하면, 다음과 같이 된다.
dt + a'u + b'v = o
이는 3차원 벡터 (t,u,v)에 대한 전형적인 선형변환이므로, 행렬 형태로 바꾸면 다음과 같다.
이때 행렬 (d, a', b')을 M이라고 쓰고, 벡터 (t,u,v)를 s라고 다시 쓰면,
Ms = o
곧, M의 역행렬을 M'이라고 하면
s= M'o
따라서, M의 역행렬을 구하고 벡터 o를 계한하여 둘을 곱하면 세 매개변수 t, u, v를 모두 결정할 수 있다. 유일한 해가 존재하고, u,v가 삼각형의 매개변수 조건을 만족하면, 직선 l과 삼각형 q는 교차한다.
이때, M의 역행렬을 구할 수 없는 경우는 직선과 삼각형이 평행하거나 삼각형이 직선을 포함하는 경우이므로, 이때는 삼각형의 세변과 직선을 직선-직선 간의 충돌 계산으로 교차 여부를 검사해야 한다.
지금까지 다뤄왔던 주제는 다음과 같다.
- STL 컨테이너
- 시간복잡도
- 컴파일 & 링크
- 프로세스와 쓰레드
- 비동기 환경에서의 문제해결
- 메모리 할당자
- 커스텀 자료구조 설계
- lua 스크립트 언어
- GUI 설계변경
- 곡선표현
- 물리연산
- 소프트웨어 설계 방법론
- 애니메이션 기법
- 커스텀 데이터 매니징
- CPU 아키텍쳐
- 회전변환
- 개발 프로세스 리뷰
다는 생각이 안나지만, 대략 이러한 종류의 주제들로 약 8개월동안 진행해 왔다. 단순계산으로 24가지 주제를 다뤄온 셈인데, 이제부터라도 기록을 남기기 위해 포스팅을 해 놓아야 겠다는 생각이 든다.
지난주의 주제는 충돌.
충돌계산의 핵심은 매개변수(parametric form) 방정식이다.
좌표평면에서 x절편 A, y절편 B를 가지는 직선의 방정식은 일반적으로 다음과 같이 쓰곤 한다.
y = -(B/A)x + B
이때 A' = -B/A 로 정의하면 간략히 다음과 같이 쓸 수 있다.
y = A'x + B
이와 같은 형태는 표현은 간단하지만, 직선이 y축과 평행한 경우는 절대로 표현이 불가능하다. 따라서, 평면에서 임의의 직선을 표현하는 좀 더 나은 방식은 음함수 형태로, 다음과 같이 쓰는 것이다.
Bx + Ay - AB = 0
이와 같은 형태는 평면상에서 임의의 직선을 표현할 수는 있지만, 특정한 조건을 만족하는 점을 계산하려면 (이를테면, 두 직선의 교점) 여러차례의 이항과 소거를 거쳐야 하는 단점이 있다. 또한 3차원 이상의 공간상에서의 직선은 이와 같은 형태로 표현이 불가능하다는 결점이 있다.
매개변수 방정식에는 위와 같은 결점이 없다. 위의 2차원 평면상의 직선은, 매개변수 t에 대하여, 다음과 같이 쓸 수 있다.
x = -At + A
y = Bt
이는 다시, 벡터 방정식으로 a=(A,0), b=(b,0)으로 정의하면, 직선 l은, 다음 식으로 표현된다.
l = (b-a)t + a
이러한 형태의 표현은 3차원 이상의 공간에서도 일반적으로 성립하며, 표기도 간단하고, 매개변수 t의 범위를 제한함으로써 선분이나 반직선등을 용이하게 표현할 수 있다. 또한 한가지 변수 t만 결정하면 직선상의 한 점을 지정할 수 있으므로, 풀이도 비교적 용이하다. 기본적인 충돌 계산은, 충돌 대상이 되는 도형을 매개변수 형태로 표현하는 것으로 시작한다.
보통 충돌 시스템을 구현할 때에는 간단한 기하도형을 몇가지 정해놓고 시작하는데, 일반적으로 다음과 같은 도형들이 충돌계산에 사용되곤 한다.
- 직선
- 선분
- 구
- 캡슐
- 실린더
- AABB
- OBB
- 삼각형
- 점
대략 9개 정도의 도형이 널리 이용되는데, 이들에 대한 구현을 모두 하려면, 각 도형이 다른 도형, 혹은 같은 도형과 충돌할 수 있으므로, 45 가지 경우를 구현해야 한다. 이에 대한 설명을 모두 하는 것은 길고 시간이 오래걸리므로, 여기에서는 직선-구, 직선-삼각형의 경우만 다룬다.
일반적으로 직선 l은, 직선의 방향벡터 d와 직선위의 한점을 가리키는 위치벡터 p가 주어질 때, 실매개변수 t에 대하여 다음 형태로 쓸 수 있다.
l = dt + p
또한 일반적인 구 s는, 중심 c와 반지름 r만으로 완전하게 정의할 수 있으므로, 구의 방정식은 벡터 형태로 다음과 같이 쓸 수 있다.
|s - c| = r
이와 같은 형태는 계산이 곤란하므로, 내적 형태로 다음과 같이 쓸 수 있다.
(s-c)·(s-c) = r*r
이때, 구 s와 직선 l의 교차점은 s = l 로 놓고 풀어 직선의 매개변수 t를 결정하는 작업이다. 구의 방정식에서 s = l을 대입하고 전개하면, t에 대한 2차방정식을 구할 수 있으므로, 이 2차방정식의 근으로 교점을 결정할 수 있다. 이 방정식이 2개의 실근을 가지면 직선은 구를 관통하며, 1개의 중근을 가지면, 직선은 구와 접하고, 허근을 가지면 직선은 구와 만나지 않는다.
3차원 공간상에서 삼각형과 직선의 충돌은 먼저, 삼각형을 매개변수 형태로 표현하는 것으로 시작한다. 삼각형 ABC에서, 벡터CA를 a, 벡터CB를 b라고하고, 점C의 위치벡터를 c라고 재명명하면, 삼각형 내부의 영역 q는, 두 매개변수 u,v에 대하여 다음과 같이 표현된다.
q = au + bv + c (u >= 0, v >= 0, 0 <= u+v <= 1 )
여기서 삼각형과 직선의 교점을 구하는 것은, 직선 l이 주어졌을 때, q = l로 놓고 풀어 직선의 매개변수 t와 삼각형의 매개변수 u,v를 구하는 문제로 바뀐다. l을 대입하면, 풀어야할 방정식이 나온다.
dt + p = au + bv + c
매개변수에 대한 항을 이항하면, 다음과 같다.
dt - au -bv = c-p
표현을 간단히 하기 위해 a' = -a, b' = -b, o = c-p 로 치환하면, 다음과 같이 된다.
dt + a'u + b'v = o
이는 3차원 벡터 (t,u,v)에 대한 전형적인 선형변환이므로, 행렬 형태로 바꾸면 다음과 같다.
| dx |
a'x |
b'x |
× |
t | = |
ox |
| dy |
a'y |
b'y |
u |
oy | ||
| dz |
a'z |
b'z |
v |
oz |
Ms = o
곧, M의 역행렬을 M'이라고 하면
s= M'o
따라서, M의 역행렬을 구하고 벡터 o를 계한하여 둘을 곱하면 세 매개변수 t, u, v를 모두 결정할 수 있다. 유일한 해가 존재하고, u,v가 삼각형의 매개변수 조건을 만족하면, 직선 l과 삼각형 q는 교차한다.
이때, M의 역행렬을 구할 수 없는 경우는 직선과 삼각형이 평행하거나 삼각형이 직선을 포함하는 경우이므로, 이때는 삼각형의 세변과 직선을 직선-직선 간의 충돌 계산으로 교차 여부를 검사해야 한다.
