Contact Points Using Clipping

http://www.dyn4j.org/2011/11/contact-points-using-clipping/

Contact Points Using Clipping
많은 사람들은 "어떻게 내가 GJK로부터 contact points를 얻는가?" 또는 SAT, GJK and EPA글에서 비슷한 것을 질문해왔다. 나는 마침내 이 주제에 대한 포스트를 만드는 것에 도착했다. Contact point generation은 많은 프로그램들의 중요한 부분이고, 보통 충돌 탐지 이후의 다음 부분이다. good contact points를 생성하는 것은 bodies 사이의 예측가능하고, life-like interactions에 중요하다. 이 글에서, 나는 Box2d와 dyn4j에서 사용된 clipping method를 다룰 계획이다. 이것은 이용가능한 유일한 방법은 아니고, 나는 글의 끝에서 다른 방법들에 대해 이야기 할 계획이다.

1. 소개
2. Features 차기
3. Clipping
4. 예제 1
5. 예제 2
6. 예제 3
7. Curved Shapes
8. Alternative Methods

Introduction

대부분 충돌 탐지 알고리즘들은 separation normal과 depth를 반환할 것이다. 이 정보를 사용하여, 우리는 그 shapes를 직접적으로 충돌을 해결하기 위해 평행이동 시킬 수 있다. 그렇게 하는 것은 실제 world physical behavior를 보여주지 않는다. 그러하듯이, 이것은 physical world를 모델링하길 원하는 프로그램에 충분하지 않다. 실제 세계 상호작용을을 효과적으로 모델링하기 위해서, 우리는 그 충돌이 어디에서 발생했는지를 알 필요가 있다.

Contact points는 보통 충돌이 발생하는 충돌중인 shapes/bodies에 있는 world space points이다. 실제 세계에서, 이것은 두 오브젝트들의 edge위에 있고, 거기에서 그 오브젝트들은 서로 닿고 있다. 그러나, 대부분의 시물레이션들은 object가 touch보다는 중첩되는 것을 허용하여 어떤 구간에서 충돌 탐지 루틴을 실행한다. 이 흔한 시나리오에서, 우리는 contacts가 무엇이 되어야 하는지를 추론해야 한다.

한 개 이상의 contact point는 일반적으로 contact manifold or contact patch라고 불려진다.

Finding the Features

첫 번째 단계는 충돌과 관련된 shapes의 features를 확인하는 것이다. 우리는 그 shape에서 가장 멀리있는 정점을 찾아서 한 shape의 collision feature를 찾을 수 있다. 그러고나서, 우리는 어떤 edge가 "가장 가까운지"를 결정하기 위해 두 개의 인접한 정점들을 본다. 우리는 그 separation normal에 가장 수직인 edge가 가장 가깝다고 결정한다.

left and right vector를 연산할 때 주의해라 (위 코드에서 l과 r). 왜냐하면 그것들은 둘 다 maximum point를 가리키기 때문이다. 만약 그렇지 않으면, 그 edge는 항상 사용될지도 모른다, 그것이 negative direction을 가리키고, 다른 것이 positive direction을 가리키기 때문에.

correct feature를 얻기위해서, 우리는 시간에 앞서 separation normal의 방향을 알아야만 한다. 그것은 A에서 B를 가리키는가? 또는 그것이 B에서 A를 가리키는가? 이것이 고정되는 것은 추천된다. 그래서 이 글에서, 우리는 그 separation normal항상 A에서 B를 가리킨다고 가정할 것이다.

Clipping

우리는 충돌에서 관련된 두 개의 edges를 가졌으니, 우리는 contact manifold (모든 contact points)를 얻는 line/plane clips을 할 수 있다. 그렇게 하기 위해서, 우리는 reference edge와 incident edge를 확인할 필요가 있다. 그 reference edge는 separation normal과 가장 수직인 edge이다. 그 reference edge는 contact manifold를 생성하는데 incident edge vertices를 clip하게 위해 상요될 것이다.

우리가 reference와 incident edges를 확인했으니, 우리는 points를 clipping하기 시작할 수 있다. 처음에, 우리는 reference edge에서 첫 번째 정점으로 incident edge의 점들을 clip할 필요가 있다. 이것은 reference vector를 따라서 그 첫 번쨰 정점의 offset을 incident edge의 offset과 비교하여 된다. 그 이후에, 그 incident edge에 대한 이전 clipping operation의 결과는 그 reference edge의 두 번째 정점을 상요하여 다시 clipped 된다. 마지막으로, 우리는 그 나머지 점들이 reference edge의 normal을 따라 reference edge를 지나는지를 체크한다. 우리는 세 개의 clipping operations를 수행한다.