Real Time Collision Detection - Chapter 3 : A Math and Geometry Primer

Chapter 3. A Math and Geometry Primer

3.1 Matrices

행렬 A는 m행 n열의 m X n 직사각형 배열이다:

행렬 항목 a ij는 배열의 i번째 행과 j번째 열에 있다.m X n 행렬은 m X n 차수라고 한다. m = n이면 A는 n차 정사각형 행렬이다.

단일 행의 행렬을 행 행렬이라고 한다. 마찬가지로 단일 열의 행렬을 열 행렬이라고 한다.

행렬은 종종 행 또는 열 행렬로 구성된다. 행 행렬 및 열 행렬은 행 벡터 및 열 벡터라고도 한다. 정사각 행렬의 경우 i = j인 항목을

행렬의 주요 대각선 항목이라고 한다. 모든 i = j에 대해 a ij = 0이면 행렬은 대각 행렬이라고 불린다.

주 대각선 행렬에 1을 입력하고 다른 모든 입력을 0으로 하는 정사각형 대각선 행렬을 I로 표시하고 항등 행렬이라고 한다.

주 대각선 위의 모든 항목이 0인 정사각형 행렬 L을 하위 삼각 행렬이라고 한다. 대신 행렬 U의 주 대각선 아래에 있는 모든

항목이 0인 경우 행렬은 상단 삼각 행렬이라고 한다.

A^T로 쓰여진 행렬 A의 전치(transpose)는 열에 대해 행을 교환함으로써 얻어지고, 그 역도 마찬가지이다.

즉 행렬 A의 전치 B는 bij = aji로 주어진다.

A^T = A이면 행렬은 대칭이다. (모든 i와 j에 대해 a ij = a ji) A^T = -A이면 행렬은 반대칭이라고 한다.

3.1.1 Matrix Arithmetic

3.1.2 Algebraic Identities Involving Matrices

3.1.3 Determinants

행렬 A의 행렬식은 det(A) 또는 |A|로 표시된 A와 관련된 번호이다. 이것은 다음 섹션에서 논의되는 것처럼 선형 방정식 시스템의

해를 결정할 때 종종 사용된다. 이 책에서 초점은 2x2 및 3x3 행렬식에 있다. 3x3 차원까지의 행렬의 경우 행렬식은 다음과 같이 계산된다:

기호 ·와 ×는 각각 내적 및 교차곱이다. 결정 요인은 기하학적으로 관련이 있다:

길이, 면적, 부피가 1D, 2D, 3D 볼륨 측정인 n X n 행렬식에 대한 n차원 공간에서의 볼륨의 일반화된 개념.

1 X 1 행렬에 대해, A = [u1], |A| 원점에서 u1까지의 선분의 부호있는 길이에 해당한다. 2 X 2 매트릭스의 경우,

|A| (u1,u2) (v1,v2) 및 (0,0)에 의해 결정되는 평행사변형의 서명된 영역에 해당하며, 마지막 점이 원점이다.

평행 사변형이 첫 번째 점에서 두 번째 점까지 반 시계 방향으로 스윕되면 행렬식은 양수이고, 그렇지 않으면 음수이다.

3 X 3 행령레 대해, A = [u w v] (여기서 u, v, w는 열 벡터) |A| 3개의 벡터에 의해 결정된 평행육면체의 부호 부착 체적에 대응한다.

일반적으로, n차원 행렬의 경우 행렬식은 행 벡터에 의해 결정되는 n차원의 초 병렬 변수의 부호 있는 하이퍼 볼륨에 해당한다.

결정 요인의 신원에 대한 전체 책이 쓰여졌다. 여기에는 다음과 같은 중요한 특징만 언급되어 있다:

- 행렬의 행렬식은 행렬이 전치된 경우에는 변하지 않는다.

- B가 A의 두 행 또는 두 열을 교환함으로써 얻어진다면, |B| = -|A|이다.

- B가 한 행(또는 열)의 배수를 다른 행(또는 열)에 추가해 A에서 파생된 경우, |B| = |A|이다.

- 두 개의 n X n 행렬 A와 B의 곱을 행렬식은 그들의 각각 행렬식의 곱, |AB| = |A||B|이다.

- A의 행(또는 열)에 상수 k를 곱해 B를 얻은 경우, |B| = k|A|이다.

- A의 한 행이 다른 행의 배수이면, |A| = 0이다. (열일 때도 마찬가지)

- 행 또는 열이 0인 행렬식의 경우, |A| = 0.

행렬식을 평가하는 효과적인 방법은 행렬에 행과 열 연산을 사용해 삼각 행렬으로 행렬을 줄이는 것이다. 

(주대각선 아래 또는 위에 있는 모든 요소가 0인 행렬)

행렬식은 주요 대각선 항목의 결과이다. 예를 들어, A의 행렬식,

다음과 같이 평가할 수 있다:

             

행렬식의 적용 예는 다음 섹션에서 설명하는 선형 방정식의 작은 시스템을 해결하기 위한 Cramer의 법칙이다. 결정 요인은 보조 요인에

의한 확장이라고 알려진 과정을 통해 평가할 수도 있다. 먼저 행렬 A에서 행 i와 열 j를 삭제해 얻은 행렬의 행렬식은 m ij가 되도록

minor를 정의한다. 그러면 cofactor c ij는:

A의 행렬식은 다음과 같이 나타낼 수 있다:

여기서 r 및 k는 임의의 행 또는 열 인덱스에 대응한다. 예를들어, 이전과 같은 행렬 A가 주어진다면, |A|는 다음과 같이 평가받을 수 있다:

3.1.4 Solving Small Systems of Linear Equation Using Cramer’s Rule

3.1.5 Matrix Inverses for 2 × 2 and 3 × 3 Matrices

역행렬에 대한 표현식에도 행렬식이 관련되어 있다. 역행렬을 계산하는 방법에 대한 자세한 내용은 이 책의 주제 범위 밖에 있다.

여기서는 2 X 2, 3 X 3 행렬에 대한 역이 다음과 같이 쓸 수 있음을 알아두면 충분하다:

3.1.6 Determinant Predicates

3.2 Coordinate Systems and Points

3.3 Vectors

3.3.1 Vector Arithmetic

3.3.2 Algebraic Identities Involving Vectors

3.3.3 The Dot Product

기하학적으로, 내적(dot product)은 v를 u로 투영한 것으로 볼 수 있으며, v의 부호있는 거리 d를 ||u||단위로 반환한다:

이 투영법은 그림 3.5a에 나와있다. 주어진 벡터 u와 v, v는 따라서 v = p + q가 되도록 u에 평행한 벡터 p와 u에 수직인 벡터 q로 분해된다:

그림 3.5b는 v가 p와 q로 분해되는 방법을 보여준다. 내적이 교환적이기 때문에 u를 v에 투영하는 것으로 보아도 마찬가지이다.

||v||의 단위로 v를 따라 u의 거리를 반환한다.

3.3.4 Algebraic Identities Involving Dot Products

3.3.5 The Cross Product

두 개의 3차원 벡터 u = (u1, u2, u3), v = (v1, v2, v3)의 교차 곱(또는 벡터 곱)은 u X v로 표시되며 벡터 성분으로 정의된다.

결과는 u와 v에 수직인 벡터이며, 크기는 u와 v의 길이와 그 사이의 각도 θ의 사인의 곱과 같다.

여기서 n은 u와 v의 평면에 수직인 단위 벡터이다. 교차 곱 w = u X v를 만들 때, w에 대해 가능한 두 가지 방향 중 하나를 선택할 수 있다.

여기에서 그리고 관습에 따라 w의 방향은 u와 v에 함께 오른손잡이 좌표계를 형성하도록 선택된다. 오른손이 w 벡터에 대해 구부러져

손가락이 u에서 v로 바뀌면 w의 방향은 확장된 엄지 손가락의 방향과 일치한다. u X v의 크기는 u와 v가 가로지르는 평행사변형의 면적과

같다. 밑면 u와 높이 v sinθ (그림 3.6)

크기는 벡터의 수직일 때 가장 크다. 행렬식에 익숙한 사람들은 교차 곱의 표현식을 pseudo-determinant로 기억하는 것이 더 쉽다:

여기서 i = (1, 0, 0), j = (0, 1, 0) 및 k = (0, 0, 1)은 좌표 축에 평행한 단위 벡터이다. 

교차 곱은 또한 행렬과 벡터의 곱으로 행렬 형태로 표현 될 수 있다.

흥미롭게도 교차 곱은 실제로 앞에서 언급 한 6 곱셈 대신 5 곱셈을 사용해 계산할 수 있다.

이 공식은 총 연산 수를 9에서 15로 증가시키기 때문에, 이러한 재작성의 실질적인 성능 이점은 하드웨어에 달려있다.

삼각형 ABC가 주어지면 두 가장자리의 교차 곱의 크기는 ABC의 두 배와 같다. 임의의 non self-intersecting 교차 사변형의 경우,

두 대각선의 외적 (e - (C - A) X (D - B))의 크기 e는 ABCD의 두 배와 동일하다. 이 속성은 그림 3.7에 나와있다.

평면에서 두 벡터에 수직인 세 번째 벡터는 평면과 2D 공간을 떠나야하므로 두 차원에서 교차 곱의 직접적인 등가물은 없다.

가장 가까운 2D 아날로그는 2D pseudo cross product이며 다음과 같이 정의된다.

여기서 u^⊥ = (-u2, u1)는 u에 수직인 반 시계 방향 벡터이다. u^⊥라는 용어는 "u-perp"라고 읽는다. 이 때문에 의사 교차 곱은 종종

perp-dot product라고 한다. 2D pseudo cross product는 스칼라로, 교차 곱의 크기와 비슷한 값은 u와 v에 의해 결정된 평행 사변형의

부호 있는 영역에 해당한다. v가 u와 반 시계 방향이라면 양수이고, v u 에서 시계 방향으로, 그렇지 않으면 0이다.

다시, (3D) 삼각형 ABC가 주어지면 교차 곱 벡터 d = (B-A) X (C-A)의 각 구성 요소는 2D 의사 교차 곱으로 구성된다.

따라서 d의 각 구성 요소는 각각 yz, zx, xy 평면에 ABC 투영의 부호가 있는 영역의 두 배를 유지한다.

따라서 단일 교차 곱 연산은 2D 점-삼각형 테스트의 결과를 결정하는데 충분하다. 교차 제품 작업이 하드웨어에서 직접 지원되는 경우 유용하다.

3.3.6 Algebraic Identities Involving Cross Products

스칼라 r과 s 및 벡터 u, v, w, x 가 주어지면 다음과 같은 교차 곱 특성이 유지된다:

3.3.7 The Scalar Triple Product

3.3.8 Algebraic Identities Involving Scalar Triple Products