기본적으로 두 개의 다면체의 밍코 스키 (minkowski) 차이의 선체에 꼭지점 집합이 있습니다. 나는 임의의 미리 결정된 방향으로 원점에서 선체까지의 거리를 찾고 싶다. Heres는 빠른 2D 스케치 : 방향에서 원산지와의 민코 소 스키 차이를 교차하면서, 얼굴이 교차하는 것을 어떻게 발견합니까?
GJK 알고리즘을 사용하여 두 객체가 교차하는지 확인하는 것이 궁금한가요? 충돌이 있다면 특정 방향 (물체의 움직임 방향)으로 침투 깊이를 찾고 싶습니다.
다면체를 광선 방향으로 투영하면 문제는 2D로 감소하고 원점을 둘러싸는 삼각형을 찾습니다. 하나의 삼각형을 테스트하려면 지정된 점선 세그먼트 (AB)가 원점을 기준으로 시계 방향 또는 시계 반대 방향으로 진행하는지 고려하십시오. 이것은 간단한 외적 시험으로 결정하기 쉽다 : 그 반대 IFF X (B-) 제품> 0
삼각형의 세 변 같은 의미있는 경우 (시계 방향 또는 시계 반 시계 방향으로) 삼각형이 원점을 둘러 쌉니다.
편집 : 당신의 다면체가 볼록이며,이 볼록하기 때문에 당신이 효율적인 방법으로 표면을 검색 할 수 있습니다 선체가
입니다. 아주 간단한 "오르막/내리막 걷기"방법으로 모서리를 가로 질러 광선을 따라 가장 멀리있는 두 개의 꼭지점을 찾을 수 있습니다. 그런 다음, Poyhedron을 투영 한 후에이 두 점에서 출발하여 원점을 향한 비슷한 오르막을 할 수 있습니다. 이것은 O (sqrt (n))입니다.
답변 해 주셔서 감사합니다. 조금 더 효율적 일 수있는 방법이 있습니까? 그것은 제곱근이 많이 있습니다. – kbirk
* Eh? * 단 하나의 제곱근 만 보았습니다. 그리고 그것은 광선을 나타내는 벡터를 정규화하는 것입니다 - 어디에서 볼 수 있습니까? 이 해법은 O (n)이다. O (sqrt (n))에 도달하는 방법이 있지만 다이어그램 없이는 설명하기가 어렵습니다 ... – Beta
아, 내 머리 속의 벡터를 섞어 도움을 주셔서 감사합니다! – kbirk