Dynamic AABB Tree 구현 (from Randy Gaul)

link : http://www.randygaul.net/2013/08/06/dynamic-aabb-tree/

Dynamic AABB Tree

물리 시뮬레이션에서 broadphase는 bodies들이 잠재적으로 언제 충돌하는지를 보고하는 일이다.

보통 이것은 간단한 bounding volume 사이의 값 싼 교차 테스트를 통해 처리된다. (이 경우에 AABBs)

구현의 관점에서 자료구조를 오히려 간단하게 만드는 dynamic AABB tree의 몇 가지 흥미로운 특성이 있다.

여기에서 개요로 보여지는 구현될 몇 가지 주요 함수들이 있다:

- Insert

- Remove

- Update

밑의 자료구조는 큰 배열의 노드들이 되어야만 한다. 이것은 많은 loose heap-allocated nodes들보다는 cache 성능 관점에서

좀 더 최적인것이다. 이것은 매우 중요한데, 노드들의 전체 배열은 그 broadphase가 업데이트되는 매 한 번마다 메모리부터

가져와질것이기 때문이다.

struct vec3
{
 float x;
 float y;
 float z;
};
 
struct AABB
{
 vec3 min;
 vec3 max;
};
 
struct Node
{
 bool IsLeaf(void) const
 {
  // The right leaf does not use the same memory as the userdata
  return right == Null;
 }
 
 // Fat AABB for leafs, bounding AABB for branches
 AABB aabb;
 
 /* 
 Information About anonymous union inside struct from 
 https://stackoverflow.com/questions/13624760/how-to-use-c-union-nested-in-struct-with-no-name
 
 For the purpose of name lookup, after the anonymous union definition, the
 members of the anonymous union are considered to have been defined in the
 scope in which the anonymous union is declared
 */
 
 union
 {
  int parent;
  int next; // free list
 };
 
 union
 {
  // Child indices
  struct
  {
   int left;
   int right;
  };
 
  // Since only leaf nodes hold userdata, we can use the
  // same memory used for left/right indices to store
  // the userdata void pointer
  void* userdata;
 };
 
 // leaf = 0, free nodes = -1
 int height;
 
 static const int Null = -1;
};
 
#define printVal(x) cout << #x << ' ' << x << '\n';
int main()
{
 Node test;
 test.parent = 0;
 test.next = 1;
 test.left = 2;
 test.right = 3;
 test.height = 4;
 printVal(test.parent);
 printVal(test.next);
 printVal(test.left);
 printVal(test.right);
 printVal(test.height);
 printVal(test.userdata);
 
 test.parent = 3;
 test.right = 270;
 printVal(test.parent);
 printVal(test.next);
 printVal(test.left);
 printVal(test.right);
 printVal(test.height);
 printVal(test.userdata);
}
 

AABB tree의 노드는 조심스럽게 최소 공간을 차지하도록 구성될 수 있다. 노드들이 항상 두 개의 상태들 중 하나에 있기 때문이다. (branch, leaves)

노드들은 한 배열에 저장되기 때문에, 이것은 노드들이 포인터 대신에 정수 인덱스로 참조되게 한다. 이것은 포인터들을 어느 곳에 매달리게

남겨두는 것의 두려움 없이 필요하다면 그 내부 배열을 증가시키거나 줄어들게 하는 것을 허용한다.

트리에 대한 아이디어는 user data가 오직 leaf nodes 내에서만 저장되도록 한다. 모든 branch nodes는 그것의 자식들 둘 다를 감싸는

한 단일의 AABB를 포함한다. 이것은 자료구조에 대한 변하지 않는 것의 짧은 묘사를 이끌게 된다:

- 모든 branches는 두 개의 유효한 자식들을 가져야 한다.

- 오직 leaves만이 user data를 포함한다.

그 첫 번째 규칙은 insert/remove 같은 연산들을 간단하게 해준다. 어떠한 부가적인 코드 branching이 NULL children을 체크하기 위해

요구되지 않고, 코드 성능을 향상시킨다.

Insert

Insertion은 새로운 leaf node와 user data를 bound시키는 fat AABB를 만드는 것을 포함한다. fat AABB는 tight fitting AABB보다는

조금 더 큰 AABB이다. 일단 새로운 leaf node가 그것의 fat AABB로 만들어진다면, 쌍으로 엮어질 형제를 찾기 위해 트리 탐색이 요구되고,

새로운 부모 branch가 구성된다.

트리를 탐색하는 것은 어느정도 cost heuristic을 따라서 처리되어야 한다. 가장 좋은 것은 관련된 노드들의 surface area를 포함하는

비용인 것처럼 보인다. cost heuristics에 있는 resource에 대한 Box2D를 보아라.

새로운 부모가 만들어지고 형제가 찾아진 후에 모든 부모 노드들의 bounding volume hierachy는 유효하지 않다.

그 트리를 위로 탐색해 모든 bounding AABB와 노드 높이를 고치는 것이 요구된다. 이 hiearchy correction은 간단한 함수로

추상화될 수 있다:

void DynamicAABBTree::SyncHierarchy(int index)
{
 while (index != Null)
 {
  int left = m_nodes[index].left;
  int right = m_nodes[index].right;
 
  m_nodex[index].height = 1 + Max(m_nodes[left].height, m_nodes[right].height);
  m_nodes[index].aabb = Combine(m_nodes[left].aabb, m_nodes[right].aabb);
 
  index = m_nodes[index].parent;
 }
}

Remove

이진 탐색 트리로부터 nodes들을 제거하는 것은 traversal path를 추적하는 stack을 포함할 수 있다.

그러나 Dynamic AABB tree의 몇 가지 불변자에 의해 제거는 꽤 간단하다. 모든 branches가 두 개의 유효한 자식들을 포함해야하만

하기 때문에, 오직 leave만이 user data를 포함하고, deletion을 요구하는 유일한 노드들은 leaves이다.

leaf의 부모를 제거하고 그것을 leaf의 형제와 대체해라. 이 연산 후에 그 부모 hierachy는 재계산 되어질 필요가 있다.

Update

이 트리는 dynamic 하기 때문에, 정적인 level geometry가 아닌 움직이는 오브젝트들을 처리하는 한 방법이 필요하다.

fat AABB는 insertion 할 때 만들어지기 때문에 오브젝트들을 트리 내에 AABB가 무효가 되기 전에 조금 움직일 수 있다.

fatness factor 또는 각 AABB를 얼마나 살찌울지에 대한 것은 성능을 위해서 미세하게 조정될 수 있다.

나 스스로는 임의의 거리를 사용한다 (약 오브젝트들의 평균 크기의 5% 정도). 또한, 오브젝트의 이전 프레임의 변위를

기반으로 AABB를 살찌우는 것이 가능하다. (displacement predictions에 대한 세부사항에 대해서는 Box2D를 보아라)

트리의 업데이트 함수는 한 도형의 현재 tight-fitting AABB가 여전히 그 트리내의 AABB에 포함되어지도록 하기 위해 체크된다.

이 연산이 상수 시간이 되게 하기 위해, 트리에 있는 노드 인덱스는 도형 내에서 그 자체로 침입해서 저장될 필요가 있다.

이것은 한 도형이 그것의 node index를 제공하는 것을 허용할 것인데 트리에 대한 최신 tight fitting AABB를 따라서 한다.

이것은 그것의 AAB가 여전히 그 fat AABB의 bounds내에 있는지를 확인하기 위해서이다.

만약 tight AABB가 fat AABB에 의해 포함되지 않다면 그 도형은 제거될 필요가 있고, 트리에 다시 삽입될 필요가 있다.

Balancing the Tree

공간 분할의 이러한 종류는 이진 탐색 트리를 포함하기 때문에 그 트리가 balanced한 그 트리는 최적으로 수행할 것이다.

그러나 너가 그 트리를 어떻게 균형을 잡을지가 중요하다. 나는 dynamic AABB trees가 tree height가 아닌

surface area의 관점에서 균형이 잡혀야 한다고 들었다. 비록 이것이 개념적으로 말이 될지라도, 나는 면적을 기반으로

트리를 어떻게 balance 할지를 확신할 수 없었다. 이것을 알고나서 나는 내가 좀 더 편안한 어떤 것으로 가기로 했었는데,

그것은 tree height를 기반으로 한 balanceing이다.

단일 노드를 balancing하는 것은 그것의 두 자식들을 보는 것을 포함한다. 각 자식의 높이가 비교되어져야 하고,

그리고 만약 한 자식이 다른 것보다 더 높다면 두 개 이상의 한 rotation의 높이 쯤이 수행되어야 한다.

다시 말해서, 더 큰 높이를 가진 자식은 promoted 되어여만 하고, 거기에서 promotion은 한 노드를 

tree hierachy 위로 회전시키는 방법이다.

Free List

트리는 사용되지 않은 노드들에 대한 내부 free list를 유지할 필요가 있다. free list를 구성하는 것은 트리의 모든 노드들에

대해 루프를 도는 것을 포함한다. 초기 tree 생성시에, 그리고 이것은 각 노드를 다음것과 인덱스들로 연결하게 한다.

이 과정은 꽤 간단하다. 독자들이 포인터의 리스트와 반대로 인덱스의 리스트에 친숙하지 않을지라도.

여기에 free lists를 설정하기 위해 내가 구현한 helper function이 있다. (트리의 구성할 때와 내부 배열을 증가시키는데 유용하다)

inline void DynamicAABBTree::AddToFreeList(int index)
{
 for(int i = index; i < m_capacity - 1; ++i)
 {
  m_nodes[i].next = i + 1;
  m_nodes[i].height = Node::Null;
 }
 
 m_nodes[m_capacity - 1].next = Node::Null;
 m_nodes[m_capacity - 1].height = Node::Null;
 m_freeList = index;
}

Queries

트리에 대해 AABB에 대한 충돌 체크가 빠른 한 volumes를 쿼리하는 것은 매우 효율적이다.

그 트리를 쿼리하는 것은 트리에 있는 각 노드와 충돌을 탐지하는 것을 포함한다. 이것은 root에서 시작해

그 트리가 다 소진될 때까지 모든 자식들을 가로지르게 된다. 한 자식을 탐색하는 것은 부모와 충돌이 있다면 수행되어야만 한다.

이러한 query는 쉽게 재귀로 처리될 수 있다. (noe : the callback은 bool을 반환하고, 그 query의 지속 또는 종료를 나타낸다)

template<typename T>
inline void DynamicAABBTree::Query(T* cb, const AABB& aabb, int id) const
{
 const Node* n = m_nodes + id;
 if (Prim::AABBtoAABB(aabb, n->aabb))
 {
  if (n->IsLeaf())
  {
   // Report, via callback, collision with a leaf
   if (!cb->TreeCallBack(id))
    return;
  }
  else
  {
   Query(cb, aabb, n->Left);
   Query(cb, aabb, n_right);
  }
 }
}

그러나, iterative algorithm 으로 그렇게 하는 것이 좀 더 선호될지도 모른다. iterative algorithms은 일반적으로

구현하기에 더 어렵지만, 메모리를 덜 자치한다. (따라서 더 효율적이다):

template<typename T>
inline void DynamicAABBTree::Query(T* cb, const AABB& aabb, int id) const
{
 const int k_stackCapacity = 256;
 int stack[k_stackCapacity];
 unsigned sp = 1;
 
 *stack = m_root;
 
 while (sp)
 {
  assert(sp < k_stackCapacity);  // k_stackCapacity too small!
  int id = stack[--sp];
 
  const Node* n = m_nodes + id;
  if (TestAABBOverlap(aabb, n->aabb))
  {
   if (n->IsLeaf())
   {
    // Report, via callback, a collision with leaf
    if (!cb->TreeCallBack(id))
     return;
   }
   else
   {
    stack[sp++] = n->left;
    stack[sp++] = n->right;
   }
  }
 }
}

Culling Queries Further

지난 프레임에서 움직였던 rigid bodies만을 쿼리하는 것은 좋은 아이디어일지도 모른다. 이것은 모든 dynamic bodies를

조건없이 쿼리하는 것보다 훨씬 더 좋다. 만약 너가 contact graph 또는 constraint graph 또는 어떤 islanding implementation을

가졌다면 너는 쉽게 queries로부터 오브젝트들을 cull 할 수 있다. 그 아이디어는 만약 rigid body가 static하거나 한 island 내에서

위치되어 있지 않다면, 그러면 그것은 모든 이전 프레임에서 움직이지 않았다는 것이다. 이것은 매우 간단하고 우아하다.

보통 오직 active (깨어있는) dynamic bodies는 island 안에 위치된다. 이것은 왜냐하면 자고 있는 오브젝트들은 새로운 island를

형성할 때 전혀 고려될 필요가 없기 때문이다. 그들이 잠들었기 때문이다. 

이것을 알아서, 그것이 island에 배치될때. 한 작은 flag이 도형 내에서 설정될 수 있다.

이 flag는 나중에 그것이 broadphase내에서 queried 될 필요가 있는지 아닌지를 알기 위해 체크될 수 있다.

비록 이 단계가 dynamic AABB tree에 대해 명백하지 않을지라도 이것은 알기에 좋은 트릭이다.

한 caveat은 contact constraints가 업데이트 될 때, 그것들은 처음에 각 연관된 shape의 bounding volume이 서로에 대해

체크되도록 해야한다. 이것은 오래된 contact constraints가 제거되도록 한다. narrow phase가 true를 반환할 잠재성이 없다면.

Conclusion

dynamic AABB tree는 매우 빠른 공간 분할 자료구조이고, 큰 unbounded worlds와 많은 dynamic rigid bodies 둘 다에 이상적이다.

Tree query하는 것은 이진 탐색의 시간 복잡도를 가진다. 나는 rigid body simulation에 대해 broadphase에 대한 더 좋은 것을 상상할 수 없다.

"no broadphase is perfect, and neither is this one"라는 오래된 격언이 있다.

성능 관점에서 나의 시뮬레이션은 100개 이상의 dynamic bodies에서 N^2 broadphase로 중단되고 병목현상을 겪을 것이다.

이제 나는 시뮬레이션 시간의 약 5%를 차지하는 broadphase로 약 5000개의 rigid bodies를 시뮬레이션할 수 있다.

나의 현재 bottleneck은 constraint solving동안의 cache misses이다.