소소한일상

임의의 두 다면체에 대해 어떤 축이 존재해서 그 축으로 다면체를 투영할시 투영 구간이 겹치지 않는다면 서로 겹치지 않는다.

A와 B가 겹치지 않는다면 다음 축들 중 하나에 평행한 축에 의해 분리된다.

1. A면중 하나의 법선 벡터

2. B면중 하나의 법선 벡터

3. A의 변과 C의 변에 동시에 수직인축

axis1의 경우 두물체를 투영시 투영부분이 겹치지만 axis2에서 겹치지 않으므로 두물체는 서로 겹치지 않는다.

구의 중점과 캡슐의 선분의 최단거리가 구의반지름 + 캡슐반지름 보다 작거나 같다면 교차

※ 선분과 점의 최단거리 구하는 방법 참조

구의 중심과 OBB 사이의 가장 가까운점과의 거리가 구의 반지름보다 작거나 같다면 교차했다고 할 수 있다.

OBB와 점 사이의 가장 가까운 거리 찾기

C : 박스의 중심

a : 박스의 각축의 정규화된 벡터

r : 박스의 길이(절반길이)

P: 임의의점

P와 C를 잇는 벡터 d를 구한다.

각축을 t에 투영하여 거리를 구한다

이거리는 박스의 범위를 넘어가지 않게 제한한다

박스의 중심C와 각축에 대해 구한 거리벡터를 모두더한 값이 가장가까운점 p'가 된다

캡슐상의 선분과 광선의 최단거리가 캡슐의 반지름 보다 작다면 교차 했다고 할수 있다.

두광선을 캡슐과의 최단거리(초록색)을 살펴보면 1번광선은 최단거리가 캡슐 반지름보다작아 교차한다.

 2번광선은 최단거리가 캡슐 반지름보다 커서 교차하지 않는다. 

광선과 OBB의 교차검출 방법중에 slabs 방법이 있다.

광선과 육면체 세방향에 대한 교점을 찾고 교점의 최대값 최소값을 비교하면된다

구한 최소값중에서 가장큰값이 최대값중에서 가장작은값 보다 작거나 같다면 광선과 박스가 교차한 것 이다.

(1) 광선과 교점의 최소값중에서 가장큰값 (tu min)이 최대값중에서 가장작은값(tv max)보다 작다.  (교차)

(2) 광선과 교점의 최소값중에서 가장큰값 (tv min)이 최대값중에서 가장작은값(tu max)보다 크다. (교차하지 않음)

광선과 면의 방향에따른 교점거리를 구하는 공식은 다음과 같다.

C : 박스의 중심

a : 박스의 각축의 정규화된 벡터

r : 박스의 길이(절반길이)

O: 광선의 시작점

v: 광선의 방향

한가지 고려해야될 상황은  광선과 박스의 면이 평행할때이다.

 가 0이라면 광선과 해당면은 평행이다 여기에서

 거나 

 이면

광선은 박스 밖에 있다는것 이므로 교차하지 않게된다.

게임에서 사용하는 충돌 박스(직육면체)의 경우 두종류로 분류할 수 있다. 

AABB (Axis Aligned Bounding Box)

축에 정렬된 직육면체

축에 정렬되어 있으므로 물체가 회전함에따라 경계를 다시 지정 해야한다

교차검출이 정밀하지 않다

교차검출이 간단하다

OBB (Object Oriented Bounding Box)

물체가 회전함에따라 같이 회전하게 된다

AABB보다 교차검출이 정밀하다

교차검출이 복잡하다

AABB와 OBB의 차이

AABB박스(초록색) OBB박스(붉은색)

AABB박스는 물체가 회전하더라도 축과정렬이되어 새롭게 범위가 지정된다.

OBB박스는 물체가 회전하면 같이 회전하게 된다.

광선의 시작점을 o 방향을 d라 할때 광선의 수식

구의중심을 c 반지름r 구상의 임의의점을 p라 할떄 구의 수식

광선과 구의 교차를 구할려면 구의수식에서 p를 광선 r(t)로 변경하면 된다.

d를 단위 벡터라 가정하면

위 식은 2차 방정식 이므로 근의 공식으로 해를 구할 수 있다. (위 식에서 b가 짝수이므로 짝수공식을 사용하면 된다) 

우리가 구한 식에서 짝수공식에 해당하는 a, b, c 는 다음과 같다.

해를 구하기 전에 판별식으로 해가 존재하는지를 확인해봐야 한다.

위 식들에의해 교차판정과 충돌지점을 구할 수 있다 . 

연산의 최적화를 위해 몇가지 고려해 볼 만한사항이 있다.

1) 광선이 구 안에서 시작할 때 무조건 교차한다고 할 수 있다.

2) 구가 광선의 뒤쪽에 있을 때 교차 하지 않을 것이다.

s가 0보다 크고 광선의 시작점이 구 밖에 있을때 구는 광선 뒤쪽에 있다고 판단할 수 있다.

3차원 공간에서 선분과 선분의 최단점(가장가까운점) 구하기

두 선분 L1과 L2가 존재할때 두선분의 최단점을 구해보자.

일단 두선분을 직선의 방적식으로 나타내면 아래와 같다.

P0과 Q0를 이은 벡터(P0-Q0)를 W0라고 하고 구한 최단점을 P(sc), Q(tc) 최단점을 이은 벡터를 Wc라고 하자

위의 직선의 방정식으로 정리하면

또한 P0 - Q0를 W0라 한다면 아래와 같이 나타낼 수 있다.

최단점을 이은 벡터 Wc는 u와 v 벡터에 직교할 것이다.

위식들을 바탕으로 연립방정식을 만들 수 있다.

수식을 간단하게 하기위해 아래와 같다라고 하고 연립방정식을 sc와 tc에 대하여 풀면된다

한가지 생각해야 할 것이 두벡터가 평행할때 이다.

이 0이라면 두벡터는 평행할 것 이다.

최종적으로 구한 sc tc값을 직선의 방정식에 대입하면 해당점을 구할수 있다.

위의 수식대로 직선의 최단점을 구할수 있다. 하지만 선분이라면 최단점이 선분의 범위를 벗어나는것을 고려해야 한다.

위의 그림처럼 최단점하나가 선분의 범위 밖에 있거나 둘다 밖에 있을수도 있다. (초록색)

이경우 선분의 시작 혹은 끝점이 최단점이 되어야한다. (붉은색)

따라서 선분범위내에 존재 하기 위해서는 sc와 tc의 의 범위가 0에서 1사이어야 한다.

0보다 작다면 선분의 시작점을 가까운점으로, 1보다크다면 선분의 끝점을 가까운점으로 해야 될 것 이다.

sc가 0일경우 Wc의 최소길이를 생각해보자

Wc는 아래와 같이 구할 수 있다.

sc는 0이므로

Wc의 최소길이를 구해야하는데 을 구하는것이 계산이 쉬워진다.

구해진 식에서 t에대한 도함수를 구하면

식을 tc에 대하여 풀면

sc가 1일 경우를 생각해 보자

구해진식에서 t에대한 도함수를 구하면

식을 tc에 대하여 풀면 

따라서 선분범위가 0~1을 벗어난다면 위의 두식으로 구할 수 있다.

선분과 점의 최단점(가장가까운점) 구하기

선분은 광선(직선)과의 차이점은 시작점과 끝점이 존재한다는 것이다.

그래서 3가지 상황을 고려해봐야 한다.

선분 양끝점을P0, P1 이라하고 임의의점 Q0, Q1, Q2가 있다고 가정하자.

광선에서 가까운점을 구할때처럼 투영해서 나온 위치를 찾는다고 한다면, Q0의 경우 선분 사이의 점이 아니게 된다.

따라서 Q0의 경우 선분위의 가장가까운점은 투영한위치의 점이 아니라 P0라고 할 수 있다.

Q1의 경우 투영한 위치에 해당하는점이 선분위에 존재함으로 광선의 경우와 같이 투영한위치의 점이 가장 가까운점 이다.

Q2의 경우 투영한위치가 선분밖에 있으므로 가장가까운점은 P1이라고 할 수 있다.

그렇다면 임의의점과 선분상의 가장가까운 점이 선분위에 있을지 밖에 있을지를 어떻게 판단 할 것인지 알아보자.

먼저 임의의점과 선분의점(P0)의 방향 벡터W를 구한다.

또한 P0과 P1의 방향벡터를 V라 하자

Q0 의 경우 선분의점(P0)과 Q0의 방향벡터 w1을 구할수 있다. (Q1 - P0)

w1과 V를 내적하게 되면 내적값은 0이하가 나올것이다. (두벡터의 각도가 90도를 넘기때문에)

따라서 W와 V를 내적한값이 0이하라면 선분의 바깥(왼편)에 있다고 할수있다.

Q1 의 경우도 마찬가지로 w2와 v를 내적해보면 나오는값이 0보다 클것이다.

여기서 한번더 고려해봐야 될 것이 임의의점이Q2일경우 여기서구한 w3벡터 또한 내적할시 0보다 클것이다.

그래서 임의의점이 P1의 범위가 넘어갔는지 어떻게 판단 할 것 인가를 생각해 봐야 한다.

W와 V를 내적한값이 V벡터의 길이제곱보다 크다면 해당점은 P1범위를 넘어갔다고 할 수 있다.

선분과 점의 최단거리(가장가까운 거리) 구하기

세가지 상황을 고려하여 최단점을 구했다면 거리도 쉽게 구할 수 있다.

광선과 점의 최단점(가장가까운점) 구하기

광선의 시작점 O 광선의 방향 D 벡터라 할때 점P와 가장가까운 광선위의 점을 구하는 방법

W벡터를 구한뒤 벡터 투영을 이용하면 구할 수 있다.

광선의 시작점과 투영된 벡터를 더하면 P'를 구할 수 있다.

 D가 단위벡터라면 |D|제곱은 생략 가능하다.

광선은 반직선이므로 투영된 위치의 점이 위와 같이 광선 범위 안에 있지 않다면

가장 가까운점은 광선의 시작점 O가 될 것이다.

값이 0보다 작을때 광선범위 밖의 점이 될 것이다.

광선과 점의 최단거리(가장가까운 거리) 구하기

P' 벡터를 구했다면 P에서 P'로가는 벡터의 거리를 구할수 있으므로 쉽게 거리를 구할 수 있다.

또는

피타고라스 정리를 이용하여 구할 수 도 있다.

※ 벡터 길이의 제곱은 그벡터를 내적한 값과 같다.

가까운 점을 구할때와 마찬가지로 값이 0보다 작을때 광선범위 밖의 점이 될 것이다.

따라서 광선의 시작점 과 임의의점을 연결한 벡터 W의 길이가 최단거리가 된다.

구와구의 교차판정은 2차원의 원과원의 교차판정에서 축이 하나더 늘었다고 생각하면된다.

두 구 중심사이의 거리가 각 구의 반지름을 더한값보다 크다면 교차안함, 같다면 딱붙은상태, 작다면 교차함 이라 할 수 있다.

구의 거리를 구하는 방법은 피타고라스정리로 간단히 구할수 있다.

또는

A B 방향 벡터를 구하여 거리를 구할수도 있다. A구의 센터가 Ca B구의 센터가 Cb라고 한다면

거리를 구했다면 거리와 A B 반지름 합을 비교하면 교차여부를 판별할 수 있다.

구와구의 교차는 간단한 수식인만큼 빠른 교차판정이 가능하다.

※ 제곱근 연산은 연산시간이 걸리는 편에 속하므로 제곱근을 하지않고 A B 반지름 합을 제곱하여 비교하면 연산량을 줄일수가 있다. 

두벡터 A B가 존재할 시 A벡터를 B에 투영한 Proj 벡터를 구하는방법

일단 벡터의 내적부터 살펴보면

벡터의 내적 : A · B = |A||B|cosθ  (A벡터 길이 * B벡터 길이  * cosθ )

※ θ 는 두벡터의 각도 이다

투영 벡터의 길이

B벡터의 단위 벡터

투영벡터의 길이에 B벡터의 단위벡터를 곱하면 투영 벡터를 구할 수 있다.

B벡터가 단위벡터(길이가1인벡터)라면 

로 구할수 있다.