Custom Physics Engine – Part 2: Manifold Generation

http://www.randygaul.net/2013/03/28/custom-physics-engine-part-2-manifold-generation/

~~
OBB to OBB
이제 큰 거에 대해서 말해보자. world에서 두 개의 OBB가 교차하는지를 어떻게 알 수 있는가? 두 개의 박스들이 방향지어져 있다. 그래서 그 문제는 많은 복잡한 계산들을 포함할 것이다. 삼각 함수 연산을 포함하여.

상황을 간단하게 해보자: 한 OBB를 다른 OBB의 reference frame으로 바꾸고, 그 변환된 object를 AABB로 다루자. 이제 그 문제는 훨씬 더 간단해 진다.

처음에 SAT check을 수행하고, 가장 적게 관통한 축을 찾아라. SAT를 수행하기 위해, 너는 너가 현재 테스트하고 있는 축으로 사영된 radius를  발견해야 한다.

만약 두 OBB로부터 그 사영된 radii의 합이 각 OBB의 센터 사이의 거리보다 더 크다면, 그러면 그것들은 그 축에서 교차하고 있는 것이다. 이 방법은 2D에서 모든 convex polygons에 대해 작동한다.

내가 이 check를 수행하는 방법은 A에서 B로가는 translation vector를 취하는 것이다. 그것을 T라고 부르자. 그러고나서 나는 T를 A의 관점으로 회전하고, A의 extent vector를 뺀다. 그리고 그 전체 결과를 A의 관점으로 회전된 B의 extent로 뺀다. 이 결과는 오브젝트 A에 대한 x와 y축을 따라 중첩을 보유한 한 벡터이다. 대칭성으로 인해, 두 축만이 테스트될 필요가 잇다. B의 separating axis를 찾기 위해 같은 연산이 오브젝트 B에 되어질 수 있다. 만약 어떠한 separating axis도 찾아질 수 없다면, 그 도형들은 교차하고 있다.

이것이 상황이 어려워지기 시작하는 곳이다. 우리가 막 early out test를 수행했기 때문에, 이제 우리는 가장 적게 관통하는 separation axis를 찾을 필요가 있다. 그러나, 너는 A에서 B로 가는 translation vector의 회전 동안 부동소수점 문제로 인해 부동소수점 비교를 수행할 수 없다. 너는 일관된 방식으로 다른 것에 대해 한 축을 옹호하기 위해 너의 비교를 bias해야만 한다. 이것은 안정성을 위해 중요하다.

위의 사진에서, 어떤 contact points/normal이 옳은 것인가? separation의 각 축은 같은 거리에 매우 근접하다. 그래서 부동소수점 에러는 어떤 축이 선택되어질 수 있는 지를 설명한다. 만약 너의 시뮬레이션이 그 둘 사이에 주저 안즌다면, 너는 이상한 jitter로 끝날 것이고, 너의 시뮬레이션은 덜 신뢰할만할 것이다. 그 솔루셔은 error EPSILON value를 사용하여 또 다른 것에 대해 한 축을 옹호하는 것이다.

여기에 어떤 값이 다른 것에 비해 더 큰지를 확인하는 함수가 있다. 각 값은 조금 수정되고, 작은 bias가 각 값이 얼마나 큰지를 기반으로 비교에 넣어진다. 이것은 다른 것에 대핸 한 separation 축을 옹호하는데 사용될 수 있다; threshold가 부동소수점 에러보다 더 클 때 까지 error는 위반된다.

조심스럽게 너의 normal이 separating axis에 따라 (A에서 B로) 어떤 방향으로 가는지를 기록해라. 이것은 위에서 보여지듯이, AABB to AABB에서 발견되는 연산과 유사하다.

한 축이 알려진다면, 두 개의 선분들이 확인되어야만 한다 : reference face와 incident face. 그 reference face는 너가 기록했던 너의 normal과 일치한다. 그래서 그 reference face는 least penetration을 가진 axis와 일치하는 face이다. 만약 least penetration의 축이 A에 있다면, 그러면 너의 reference face는 A에 있다. 그 incident face는 우리가 manifold를 생성하는데 필요한 정보를 가진 것이다.

그 incident face는 다른 오브젝트에 있는 face이고, reference face가 부딪히는 곳이다. 우리는 그것을 연산해야만 한다. 처리되어야 할 것은 어떤 face가 그 normal를 만나고 있는지이다 (가장 negative dot product를 가진 것). 내적을 수행하여 모든 faces에 대해 반복하는 것은 이것을 성취하는 가장 간단한 방법이다. 좀 더 최적화된 알고리즘은 flipped normal의 부호를 따르는 것이다. 너의 normal은 x와 y component를 갖는다 (3D에서는 z도), 그리고 각 컴포넌트는 양수 또는 음수일 것이다. 이것은 너에게 양수 또는 음수의 네 개의 조합을 준다.

처음에 그 normal이 x축 또는 y축을 향하는지를 보아라 (너가 그것을 incident face의 관점으로 변환한 후에). 그러고나서 y축의 부호를 체크해라. 너는 너의 normal이 어떤 face를 가리키고 있는지를 알게 된다.

그것을 이 방식으로 생각해라: 만약 그 normal이 x축을 향해 가리키고 있따면 (n.x의 절댁밧이 n.y의 절대 값보다 더 크다면), 그러면 너는 너의 OBB에서 왼쪽 또는 오른쪽 face 둘 중 하나를 가리킬 것이다 (OBB의 관점에서). 너가 거기에서 알 필요가 있는 것은 너가 X축에서 왼쪽 또는 오른쪾을 가리키냐이고, 이것은 normal의 기호료 표기된다.

너의 incident face segment endpoints는 OBB의 x축의 extents이다. 그리고 그 OBB는 OBB의 관점에서 X축과 정렬된다. 너는 그러고나서 그 OBB의 x half-extent를 취하고 두 점을 형성하기 위해((-x,0), (x,0)) 그것의 positive and negative version을 사용할 수 있다. 거기에서 x는 그것의 x축에 있는 OBB의 half-extent이다. 이러한 점을 OBB의 rotation matrix로 회전시키고, 그러고나서 그것들을 OBB의 position vector로 world space로 평행이동 시키고, 그리고 너는 이제 너의 incident face에 대한 끝점을 world space에서 가진다.

남은 것은 Sutherland-Hodgman clipping을 사용하여 reference face side planes에 대해 incident face를 clip하는 것이다. 여기에 이것을 보여주는 그림이 있다.

너가 수학을 꽤 잘 알지 못한다면, 이것은 꽤 어려운 것이다. 각 side plane은 너가 너의 reference normal를 알기만 한다면 간단히 연산될 수 있다. 여기에 두 side planes를 얻는 과정이 있다.

위의 코드는 내가 손으로 쓴 것이지만, 너는 Box2D Lite 내에서 비슷한 것을 볼 것이다 (거기에서 나는 원래 수학을 배웠다). 만약 이것이 너에게 혼란스럽다면, 나는 2D에서 직선에 대한 다양한 표현 유형들을 읽기를 제안한다.

여기에 나의 source files에서 발견했던 또 다른 다이어그램이 있다:

너는 내가 c value를 저장하는 것을 눈치 챘을지도 모른다. 이것은 중요한데, c값이 line structure 내에 저장될 수 있고, 그 line으로 가는 점의 거리를 찾는데 상요될 수 있기 때문이다:

나는 친절해서, 너에게 내가 Sutherland Hodgman clipping에 대해 만들었던 clipping notes를 너에게 제공할 것이다.

그러나 우리는 한 line을 signle plane으로 clipping하고 있기 때문에, 그 알고리즘은 다소 수정될 필요가 있다. 어떤 경우에서, 너는 추가 점들을 넣을 필요가 있다. 왜냐하면 Sutherland-Hodgman은 한 loop에 있는 두 폴리곤들을 clipping하는 것을 가정한다. incident의 line clipping에 대한 좋은 구현을 위해 Box2D Lite를 보아라. 나는 그러나, 매우 비슷한 방법으로 작동하는 내가 쓴 알고리즘을 사용한다. 나는 한 선분을 직선으로 clipping하는 슈도코드를 공유할 것이다. 그리고 그 line이 offset c와 normal n의 format에 있다고 가정한다.

side planes으로의 clipping 후에, floating point error는 처리되어야만 한다. 만약 우리의 clipping procss가 기대했던 대로 간다면, 우리는 두 개의 최종 점들을 가져야 한다. 만약 우리가 두 개의 output points보다 작게 가진다면, 그것은 floating point error가 우리를 망쳤다는 것을 의미하고, 우리는 그 전체 프로세르를 마치 두 개의 OBB가 교차하지 않는 것처럼 다뤄야 한다.

우리는 우리의 CLIPPING으로부터 두 개의 point output을 가진다고 가정하여, 우리는 reference face 뒤에 있는 점들만을 고려할 필요가 있다. 이것을 체크하기 위해 내가 제공한 DistanceToLine 함수를 사용해라. 그 reference face 뒤에 있는 각 점은 contact point로서 기록된다.