어떤 Plane 위의 모든 점과, 이 점들을 잇는 벡터는 Plane Normal n에 대해 수직이다.→ 이것을 이용해서 아래 Plane equation을 유도할 수 있다. = Plane 상의 어느 벡터와 노멀 n 의 dot product는 0이다.
Ax + By + Cz = D
위와 같은 평면의 방정식이 주어졌다고 하자.
평면 상의 모든 점 x, y, z는 위 방정식을 만족한다,
이 평면의 Normal Vector는 아래와 같다.
Ai + Bj + Ck
(여기에서 i, j, k는 기저 벡터를 의미)
D는 평면의 노멀 벡터, 즉 기울기에 영향을 주지 않는다 - 원점으로부터 얼마나 shift 되어 있는지만 결정할 뿐이다. D의 값이 무엇이 됐든, 같은 노멀을 가진 평면이 무한히 존재할 수 있다.
평면의 노멀 벡터와 평면 상의 한 점을 이용해 평면의 방정식 구하기
노멀 벡터 N = [1, 3, -2]
평면 위의 점 X = [1, 2, 3]
이라고 할 때, 위 두 개의 백터로 평면의 방정식을 어떻게 구할까?
평면 상의 또다른 점[x, y, z] 를 상정한다. 이 점으로부터 점 X 를 향하는 벡터를 구한다. [1, 2, 3] - [x, y, z] = [1-x, 2-y, 3-z]
이렇게 구한 벡터와 노멀 벡터의 내적은 0이다. 이 식을 활용한다. [1-x, 2-y, 3-z] dot [1, 3, -2] = 0 = 1-x + 6 - 3y - 6 + 2z = 0 = 1-x - 3y + 2z = 0 = -x -3y +2z = -1 → x + 3y - 2z = 1 가 이 평면의 방정식이 된다. 노멀 벡터와 각 계수를 비교해 보면 알 수 있다.
Plane 클래스는 Plane Normal, Plane Shift의 속성을 갖는다. Plane Normal은 Unit Vector로 유지되도록 할 것이다.
Geometry
Cross Product로 Line - Line Intersection 여부 판단하기
두 선분 (segment) 가 교차하는 지 여부를 어떻게 알 수 있을까?
두 점 A, B로 이루어진 선분 AB는 B-A로 표현할 수 있다. 아래 그림을 보자.
점 B에서 점 A의 좌표를 뺀 것이 선분 AB를 나타내는 벡터가 된다.
(AB = B - A)
이렇게 나타낸 벡터는 선분 AB의 Directional Vector이기도 하다. (A 가 선분의 시작점이 되었음에 주의하자)
이제 선분을 벡터로 나타냈으니, 주어진 점의 좌표에 대해서 벡터 계산을 수행할 수 있다.
선분 AB, CD 가 교차한다면,
점 A와 B는 선CD를 기준으로 서로 반대쪽에 있어야 한다.
점 C와 D는 선AB를 기준으로 서로 반대쪽에 있어야 한다.
위 두 조건을 모두 만족해야 두 선이 교차한다고 볼 수 있다. 각 점이 선분의 어느 쪽에 위치하는지는 위에서 본 벡터 간 외적 결과의 부호를 활용한다.
예를 들어, 선분 AB와 점 C 사이의 상대적인 위치를 알고 싶다면, 아래 두 벡터를 비교하면 된다.
A → B와 A → P 벡터를 구한 뒤, 이 두 벡터의 외적 결과의 부호를 본다.
외적의 결과가 양수라면 반시계방향, 음수면 시계방향에 위치한다.
XOR - 두 boolean 값이 서로 다를 때만 1을 반환한다. 같으면 0을 반환한다.
각 선분에 대한 점의 상대적인 위치를 XOR로 비교한다 - 점의 방향을 비교했을 때 모두 1이 나와야 한다.
구현
편의를 위해 YZ 평면에서만 비교해 보았음
Cross Product 의 부호를 비교해서 각각 A와 B가 CD 의 반대편에, C와 D가 AB의 반대편에 있으면 두 선분이 서로 교차한다고 판단
두 선분이 YZ 평면에서 교차하지 않을 때두 선분이 YZ 평면에서 교차할 때 (= 카메라가 바라보는 평면이 YZ)
Intersection Point 위치 알기
점 a 와 b로 이루어진 선분 AB 는 (b-a) 로 표현할 수 있다.교차점 P는 선분 CD 위에 있다.
만약 이 선분이 다른 선분 CD 와 교차한다고 했을 때, 교차점을 구해 본다.
선분 CD에 수직인 노멀 벡터 n이 있다.
(2D 평면상의 Normal Vector : (x, y) → (y, -x)
CD = d - c 이고, 이 벡터의 (y, -x) 를 구한 것이 수직인 벡터이다. 선분 CD 위의 어느 점 혹은 벡터와, 이 노멀 벡터와의 내적은 0이 될 것이다.
즉,
이다. P(t) - c 는 c → 교차점으로 가는 Direction Vector이다. 이 방향 벡터 또한 선분 CD 위에 있다. 교차점 P는 P(t) = (b-a)t + a 로 표현 가능하다. P(t) 라는 선분을 parametric equation으로 표현했을 때 아래와 같다. P(t) = vt + a
v는 a로부터 시작되는 선분의 Directional Vector이다. t는 parameter이다. 이 값을 알면 점P의 좌표도 알 수 있다.
이것을 (b-a)t + a로 확장할 수 있다.
t에 대해 정리한 위 식을 풀어 t를 구한다.
첫 번째 각도가 분자, 두 번째 각도가 분모가 된다.
여기에서 분모 n(b-a) (그림에서의 2번째 각도)에 관해 좀 더 살펴보자.
만약 이 값이 0이 된다면, n과 선문 AB의 Directional Vector의 dot product가 0이라는 의미이므로, n은 선분 AB의 노멀 벡터도 된다는 의미가 된다. 이 경우는 선분 AB 와 CD가 평행하거나, 직선상에 나란히 있을 때만 일어난다.
→ t를 구하면, vt+a (=(b-a)t + a) 도 구할 수 있다. 이것이 교차점의 좌표가 된다.
구현
1. 선분 CD 의 Normal Vector 를 구한다.
n = FVector2d((d-c).y, (d-c).-x)
이것을 Direction Vector로 한 선분을 Spawn한다.
선분 CD 의 Normal Vector를 구해 파란 선으로 표시하였다.
2. n에 대해 다음 식을 만족하는 t 값을 구한다.
3. t를 선분 AB에 대입해서 선분 AB 상의 점의 좌표를 구한다. 이것이 교차점의 위치가 된다.
Update T에서 t에 따른 선 위의 좌표를 구하는 부분은 아래와 같다.
Direction * t + StartPoint (a)
두 선 사이의 각도 계산하기
2D 공간 안의 두 선은 어느 지점에선가 교차하거나, 평행이다.
평행일 경우, 두 선 사이의 각도는 0이다.
두 선의 Directional Vector가 주어지면, 여기에서부터 각도를 계산할 수 있다.
3D에서는 어떨까?
2D 에서와 계산은 같다. 다만, 선이 교차하거나, 평행하거나, 또는 꼬일(skewed) 수 있다. - 평행하지도 않고, 교차하지도 않는다.
Plane 과 Line 간의 각도 계산하기
두 Line 사이의 각도를 계산할 수 있다면, 이것을 이용해 Plane 과 Line 간의 각도도 계산할 수 있다.
Line의 Directional Vector 와 Plane Normal Vector 사이의 각도를 계산할 수 있다. 이 각도를 a라고 할 때, 90 - a 가 우리가 원하는 Plane 과 Line 간의 각도가 된다.
두 Line 사이의 각을 계산할 때, 아래 식을 다시 사용한다.
두 Directional Vector가 Normalize 되어 있다면, 분모 |u||v| 는 1이 된다. 따라서 식은 아래와 같은 모양이 된다.
이 theta (in degree)에서 -90 한 것이 Line 과 Plane 사이의 각도가 된다.
Colinear, Coplanar
Colinear
두 벡터가 서로 평행하거나, 점 두 개가 1개의 라인상에 있음
직선 두 개가 서로 평행할 경우, Colinear함
한 벡터를 다른 벡터의 곱인 u = kv 형태로 표현 가능.
u = [x1, y1, z1], v - [x2, y2, z2] 일 때,
x1/x2 = y1/y2 = z1/z2
를 만족해야 함.
이 식을 정리하면, x1y2 - y2x1 = 0 같은 식이 3개 생성됨
→ 0인지 아닌지 검사하면, Colinear 인지 아닌지 판별할 수 있음
Coplanar
벡터들이 한 평면 위에서 평행하거나, 같은 평면에 놓여져 있음
모둔 벡터 두 개는 한 개의 평면을 공유함.
벡터가 3개일 때, 이 벡터들이 이루는 tetrahedron의 부피는 0이 됨
A벡터와 B백터가 공유하는 Plane 위에 C 벡터가 위치한다면, 이 세 벡터는 coplanar 임
A, B, C, D 점이 이루는 tetrahedron의 부피는 아래와 같이 구한다.
= Scalar Triple Product.
결과의 부호는 벡터들의 순서에 따라 결정된다.
점과 선 사이의 거리
점과 점 사이의 거리는
로 구할 수 있다.
만약 어떤 선과 점 사이의 거리를 알고 싶다면, 선에서 점과 가장 가까운 위치의 점을 구한 뒤, 이 점과 원래 점 사이의 거리를 구하면 된다.
점과 선 사이의 거리는, 선분 상에서 점에 가장 가까운 거리의 좌표와 점 사이의 거리이다.
이 좌표와 점 사이를 잇는 벡터는, 선과 직각을 이루므로 내적의 결과가 0이다.
선 위에서 점으로 향하는, 직각의 선을 찾는다. 이 선분과 원래의 선분의 Intersection Point를 찾는다.
선분 위의 Intersection Point가 X(t)라고 했을 때,
이다. (v는 제시된 선의 의 Normalize 된 Directional Vector 이다)
점을 Y라고 했을 때, Y - X(t) (=Y - (vt - a))가 선분과 직각을 이루는 선이다. 이 선과 원래의 선을 내적했을 때 0이 되어야 한다. 이것을 아래와 같은 식으로 나타낼 수 있다.
여기에서 a는 Intersection Point 의 좌표이다.
같은 벡터끼리 내적했을 때, 그 결과는 magnitude의 제곱이 됨을 이용하면, 아래와 같이 식을 세울 수 있다.
(v dot v 와 t1를 오른쪽 항으로 옮긴 것이다) 여기에서 t1은 Intersection Point의 t값을 의미한다.
이 식을 정리해서 t1값을 유도할 수 있다.
여기에서 v는 제시된 선분의 Directional Vector이고, a는 그 선 위의 Known Point 이다.
(Line Type이 Ray 또는 Segment 인 경우 a = Line StartPoint로 정의하였다)
이렇게 구한 t1을 제시된 선분의 Parametric equation 에 대입하면, Intersection Point를 알 수 있다.
Y - X(t) 벡터의 길이를 구하면, 그것 또한 점과 선 간의 거리가 된다.
Ray의 경우,
t가 음수라면 Ray 의 Start Point 보다 뒤에 있는 것이기 때문에, 가장 가까운 점은 Ray의 Start Point가 된다. 거리는 Start Point로부터 점 까지가 된다.
Segment 의 경우,
Parametric Equation에서 t 값은 0부터 1 까지로 제한된다.
만약 교차점 $t_1$이 0과 1 사이의 범위 안에 있지 않다면, 선분 상에서 더 가까운 endpoint 를 찾고 그 거리를 취한다.
