3D 충돌 / 물체 감지는 어떻게 작동합니까?
나는 항상 이것을 궁금해했다. 수만 개의 개체가있는 GTA 와 같은 게임에서 체력 팩을 착용하자마자 게임이 어떻게 알 수 있습니까?
각 객체에 대한 이벤트 리스너가있을 수 없습니까? 반복하는 것도 좋지 않습니까? 나는 그것이 실제로 어떻게 이루어 졌는지 궁금합니다.
이에 대한 답은 하나도 없지만, 큰 세계는 종종 선형 시간 (분수 거듭 제곱 또는 최악의 경우 O (N ^ ()에서 가장 가까운 이웃을 찾기위한 검색 시간을 가져 오는 쿼드 트리 또는 kd- 트리 의 선을 따라 무언가를 사용하여 공간 분할됩니다. 2/3)) 3D 게임). 이러한 방법 을 이진 공간 분할을위한 BSP 라고 합니다.
충돌 감지와 관련하여 각 개체에는 일반적으로 연결된 볼륨 메시 (볼록 껍질을 형성하는 다각형 집합)가 있습니다. 이러한 매우 단순화 된 메시 (때로는 단지 큐브)는 그려지지 않지만 충돌 감지에 사용됩니다. 가장 기본적인 방법은 각 개체의 중간 점을 선의 중간 점에서 선과 교차하는 평면과 연결하는 선에 수직 인 평면을 만드는 것입니다. 오브젝트의 경계 볼륨에이 평면의 양쪽에 점이있는 경우 충돌입니다 (평면에 대해 두 경계 볼륨 중 하나만 테스트하면 됨). 또 다른 방법은 향상된 GJK 거리 알고리즘입니다. 튜토리얼에 대해 자세히 알아 보려면 NeHe Productions의 OpenGL 강의 # 30을 확인하십시오 .
덧붙여, 경계 볼륨은 폐색 쿼리 라고하는 것과 같은 다른 최적화에도 사용할 수 있습니다 . 이것은 다른 개체 (폐쇄기) 뒤에있는 개체를 결정하는 프로세스이므로 처리 / 렌더링 할 필요가 없습니다. 경계 볼륨은 또한 어떤 오브젝트가 원근보기 볼륨 외부에 있는지 (너무 가깝거나 너무 멀거나 시야각을 넘어서) 렌더링 할 필요가없는 것을 결정하는 프로세스 인 절두체 컬링 에도 사용할 수 있습니다 .
Kylotan이 지적했듯이 경계 볼륨을 사용하면 폐색을 감지 할 때 오 탐지가 발생할 수 있으며 토 로이드와 같은 일부 유형의 물체 (예 : 도넛의 구멍을 통해 보는 것)에 대해 전혀 작동하지 않습니다. 이러한 객체가 올바르게 가려지는 것은 portal-culling의 다른 스레드입니다 .
Quadtrees 및 Octrees , 또 다른 quadtree 는 공간 분할을 사용하여이를 수행하는 인기있는 방법입니다. 이후의 예는 충돌에 대한 쌍별 무차별 대입 검색을 통해 처리가 97 % 감소한 것을 보여줍니다.
게임 물리 엔진의 일반적인 기술은 스윕 앤 프룬 방법입니다. 이것은 David Baraff의 SIGGRAPH 노트에 설명되어 있습니다 (제약 조건이있는 모션 장 참조). Havok은 확실히 이것을 사용합니다. Bullet의 옵션이라고 생각하지만 PhysX에 대해서는 잘 모르겠습니다.
아이디어는 각 축에서 AABB (축으로 정렬 된 경계 상자)의 겹침을 볼 수 있다는 것입니다. 두 개체의 AABB 투영이 세 축 모두에서 겹치면 AABB가 겹쳐 야합니다. AABB의 시작점과 끝점을 정렬하여 각 축을 비교적 빠르게 확인할 수 있습니다. 일반적으로 대부분의 개체가 매우 빠르게 이동하지 않기 때문에 프레임 사이에 많은 시간적 일관성이 있으므로 정렬이 많이 변경되지 않습니다.
청소 및 가지 치기가 AABB 사이의 겹침을 감지하면 물체 (예 : 구 대 상자)에 대해 더 자세한 검사를 수행 할 수 있습니다. 세부 검사에서 충돌이 발견되면 힘을 적용하여 충돌을 해결하거나 게임 이벤트를 트리거하거나 사운드 효과를 재생할 수 있습니다.
옳은. 일반적으로 각 객체에 대한 이벤트 리스너는 없습니다. 종종 게임 맵을 모방하는 메모리에 바이너리가 아닌 트리 구조가 있습니다. 지하철 / 지하지도를 상상해보십시오. 이 메모리 구조는 게임에있는 것들의 모음입니다. 당신은 플레이어, 몬스터 및 픽업 할 수있는 아이템 또는 폭발 할 수있는 아이템으로 해를 끼칠 수 있습니다. 따라서 플레이어가 게임 주위를 이동할 때 플레이어 개체 포인터는 게임 / 맵 메모리 구조에서 이동합니다.
내 게임 엔터티가 주변에 대해 알고 있어야하는 방법을 참조하십시오 .
실시간 충돌 감지에 대한 Christer Ericson의 견고한 책을 추천하고 싶습니다. 충돌 감지의 기초를 제시하는 동시에 현대 연구 노력에 대한 참고 자료를 제공합니다.
실시간 충돌 감지 (대화 형 3D 기술의 Morgan Kaufmann 시리즈)
많은 최적화를 사용할 수 있습니다. 첫째 - 모든 객체 (인덱스 I 예컨대 말할)의 중심 좌표와, 큐브에 의해 제한되어 CXi, CYi및 크기 Si둘째 - 추정 충돌 검출 방법 :
a) 조건이있는 모든 쌍 큐브 i, j 찾기 : Abs(CXi-CXj)<(Si+Sj) AND Abs(CYi-CYj)<(Si+Sj)
b) 이제 우리는 a)에 들어간 쌍으로 만 작업합니다. 우리는 Sqrt(Sqr(CXi-CXj)+Sqr(CYi-CYj))큐브, 구, 원뿔 과 같은 몇 개의 단순한 도형 집합으로 표현되는 개체 와 같이 개체 간의 거리를보다 정확하게 계산 하고 기하 공식을 사용하여 이러한 도형 교차를 확인합니다.
c) 교차로가 감지 된 b)의 객체는 물리 계산 등과의 충돌로 처리됩니다.
참조 URL : https://stackoverflow.com/questions/1960560/how-does-3d-collision-object-detection-work
'programing' 카테고리의 다른 글
| CSS Calc 뷰포트 단위 해결 방법? (0) | 2021.01.15 |
|---|---|
| R에서 이메일을 어떻게 보내나요? (0) | 2021.01.15 |
| 사용자 컨트롤과 Windows Form (0) | 2021.01.15 |
| POJO를 확장하여 JPA 엔티티를 구축 할 수 있습니까? (0) | 2021.01.15 |
| Vim : 병원체의 vimball 플러그인 권장 사항 (0) | 2021.01.15 |