선체와 상자 사이의 가장 가까운 거리

Question

볼록 선체와 축 정렬 상자 사이의 가장 가까운 거리를 찾는 가장 좋은 방법은 무엇입니까? 가장 가까운 거리는 서로 가장 가까운 선체와 상자의 한 쌍의 점을 의미합니다. 우리는 선체와 상자가 교차하지 않는다는 것을 알고 있다는 것을 알고 있다고 가정 할 수 있습니다.

선체는면, 정점으로 주어지며 필요한 경우면을 삼각형화할 수 있습니다.

Answer 1

여기에있는 종이는 두 개의 볼록한 선체 사이에서 가장 가까운 쌍을 찾는 알고리즘을 제공합니다. http://realtimecollisiondetection.net/pubs/SIGGRAPH04_Ericson_GJK_notes.pdf

AABB가이 알고리즘을 불필요하게 만드는 선체 중 하나 일 수 있다고 생각했습니다. 불행히도, 나는 그것이 사실이라는 것을 발견하지 못했습니다.

이 알고리즘의 배경은 Minkowski의 두 선체 차이점입니다. 가장 가까운 쌍은 Minkowski 차이에서 원점에 가장 가까운 점이됩니다. Cartheodory의 정리에 따르면, d 차원 공간에서 선체의 한 지점을 나타내는 데 d + 1 점만 있으면됩니다. 그래서 기본적으로 minkowski 차이의 d + 1 크기 세트를 선택하고 원점까지의 가장 가까운 거리를 찾습니다. 원점에 가장 가까운 점은 반복 알고리즘을 통해 찾습니다.

Answer 2

상자 (또는 다른 볼록 객체) 내부 선체의 경우를 들어

가 선체의 정점, 얼굴의 절대 중간 것 선체에서 가장 가까운 지점보다 교차하지 않는 경우

.

선체의 모든 꼭지점을 반복하고 상자의 각면에 계산 거리를두면 점의 쌍 (상자의면에있는 선체 + 꼭지점)을 찾을 수 있습니다. 선체의면이 상자의면 중 하나와 평행하다는 점에 유의하십시오. 동일한면에서 두 개 이상의 쌍을 얻을 수 있습니다. 외부 상자

선체 :

쌍의 제 2 목적 또는 상자와 선체의 에지 점의 지점을 포함한다. 선체와 상자의 모든 모서리를 반복하고 다른 객체의 모든면과의 거리를 계산하면 접근 방식과 비슷하지만 더 나은 것이 존재해야합니다.