AABB 충돌 검사 물리 엔진을위한 최상의 데이터 구조는 무엇입니까?

Question

축 정렬 경계 상자 (AABB)가 채워진 세계로 구성된 엔진이 필요합니다. 연속 루프는 다음과 같은 일을 실행한다 :

for box_a in world 
    box_a = do_something(box_a) 
    for box_b in world 
     if (box_a!=box_b and collides(box_a, box_b)) 
      collide(box_a, box_b) 
      collide(box_b, box_a) 

그

의 문제가 분명하고,이 O인지 (N^2). 나는 덩어리의 공간을 분할 훨씬 더 빨리이 루프를 만들기 위해 관리, 그래서이되었다 :

for box_a in world 
    box_a = do_something(box_a) 
    for chunk in box_a.neighbor_chunks 
     for box_b in chunk 
      if (box_a!=box_b and collides(box_a, box_b)) 
       collide(box_a, box_b) 
       collide(box_b, box_a) 

이 훨씬 빠르게하지만, 약간의 원유. 많은 노력이 필요없는 빠른 알고리즘이 있다는 것을 감안할 때, 내가 알지 못하는 데이터 구조가이 알고리즘에 대해 훨씬 뛰어난 확장 성을 제공하면서 여기서 수행 한 것을 일반화 할 수있을 것입니다.

내 질문은 다음과 같습니다.이 문제의 이름은 무엇이며이를 구현하기위한 최적의 알고리즘과 데이터 구조는 무엇입니까?

Answer 1

이것은 사실 컴퓨터 과학의 일반적인 문제입니다. 공간 분할입니다.

레이 트레이싱, 래스터 렌더링, 물리학, IA 게임에 사용되며 HPC, 데이터베이스, 매트릭스 수학, 과학 (분자, 약국 ...)에 관계없이 확실히 사용됩니다. 물건.

구조가 없으므로 레이저 스캐너 (수십억 데이터)에서 나오는 클라우드 지점을 테셀레이션하는 알고리즘을 마스터 한 친구가 있는데 그의 경우 최상의 데이터 구조는 유니폼의 컬렉션 일부 octree와 3D 그리드입니다.

다른 사람들의 경우 kd-tree가 가장 좋으며, 다른 사람들에게는 BVH 나무가 가장 좋습니다.

저는 그리드 시스템을 좋아하지만 모든 셀이 존재해야하기 때문에 공간이 너무 넓 으면 작동하지 않습니다.

언젠가는 해시 맵을 사용하여 스파 스 그리드 시스템을 구현했는데 성능이 좋지 않거나 조사 할 필요가 없으므로 성능이 좋았습니다. .

기본적으로 3D 위치 벡터 해셔 인 KEY 클래스를 만들고, 먼저 좌표에 정수 나누기를 적용하여 하나의 격자 셀의 크기를 정의합니다. 그런 다음 어리석게도 모든 좌표를 하나의 해시로 해시하고 hash_value 메서드 또는 friend 메서드를 제공합니다. 항등 연산자 및 해시 맵에서 사용할 수 있습니다.

google::sparse_map 또는이 줄을 따라 쓸 수 있습니다. 나는 개인적으로 boost::unordered을 사용했으며 내 경우에는 충분했다.

그런 다음 고려해야 할 것은 AABB가 둘 이상의 셀에 존재한다는 것입니다. AABB에서 다루는 모든 셀에 참조를 저장할 수 있습니다. 모든 알고리즘에서 인식해야 할 것입니다. "셀 참조와 AABB 간에는 1-1 개의 관계가 없습니다." 그게 다야.

행운