Dynamic AABB Tree 구현 (from Randy Gaul)

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

Dynamic AABB Tree
Box2D, Bullet 그리고 DigiPen 출신인 한 졸업생(Nathan Carlson덕택에) 몇 가지 슬라이들을 공부한 후에, 나는 dynamic AABB (axis aligned bounding box) tree broadphase를 합쳤다. Dynamic AABB Tree는 공간 분할을 위한 이진 탐색 트리이다. Bullet engine 내에서 트리 소스 코드의 원잔자인 Nathanael Presson에 특별한 감사의 말을 전한다. (이 포스트의 커멘트들을 보아라).

물리 시뮬레이션에서 broadphase는 bodies들이 잠재적으로 언제 충돌하는지를 보고하는 일이다. 보통 이것은 간단한 bounbding volume 사이의 값 싼 교차 테스트를 통해 처리된다 (이 경우에 AABBs)

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

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

• Insert
• Remove
• Update

밑의 자료구조는 큰 배열의 노드들이 되어야만 한다. 이것은 많은 loose heap-allcoated 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);
}

{
내가 처음 보는 문법이 있어서 테스트 예제도 덧붙였다. 저걸 출력하게 된다면,

이렇게 된다, 스택 오버플로우에서 가져온 주석 내용 처럼, 멤버로 인식하는데, union scope 내에 있는 것은 서로 영향받게 된다.
}

AABB tree의 노드는 조심스럽게 최소 공간을 차지하도록 구성될 수 있다, 노드들이 항상 두 개의 상태들 중 하나에 있기 때문이다: branches와 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 hierarchy는 유효하지 않다.  그 트리를 위로 탐색하여, 모든 bounding AABB와 노드 높이를 고치는 것이 요구된다. 이 hierarchy 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가 두 개의 유효한 자식들을 포함해야만 하기 때문에, 오직 leaves만이 user data를 포함하고, deletion을 요구하는 유일한 노드들은 leaves이다.

leaf의 부모를 제거하고, 그것을 leaf의 형제와 대체헤라. 이 연산 후에, 그 부모 hierarchy는 재 계산 되어질 필요가 있다 (insert에서 했던 것처럼)

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를 따라서 한다, 이것은 그것의 AABB가 여전히 그 fat AABB의 bounds내에 있는지를 확인하기 위해서이다.

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

Balancing the Tree
공간 분할의 이러한 종류는 이진 탐색 트리를 포함하기 떄문에, 그 트리가 balanced(균형이 잡힌)한, 그 트리는 최적으로 수행할 것이다 (쿼리의 관점에서)

그러나, 너가 그 트리를 어떻게 균형을 잡을지가 중요하다. 나는 dynamic AABB trees가 tree height가 아닌 surface area의 관점에서 균형이 잡혀야 한다고 들었따. 비록 이것이 개념적으로 말이 될 지라도, 나는 면적을 기반으로 트리를 어떻게 balance할지를 확신할 수 없었다. 이것으 ㄹ알고나서, 나는 내가 좀 더 편안한 어떤 것으로 가기로 했었는데, 그것은 tree height를 기반으로 한 balancing이다.

단일 노드를 balancing하는 것은 그것의 두 자식들을 보는 것을 포함한다. 각 자식의 높이가 비교되어져야 하고, 그리고 만약 한 자식이 다른 것보다 더 높다면, 두 개 이상의 한 rotation의 높이쯤이 수행되어야 한다. 다시 말해서, 더 큰 높이를 가진 자식은 promoted되어야만 하고, 거기에서 promotion은 한 노드를 tree hierarchy위로 회전시키는 방법이다.

balancing의 (AVL balancing) 이 종류는 hierarchy synchronization loop의 시작에서 수행되어질 수 있다. 이것은 트리가 삽입과 leaves의 제거 시에 그 자체로 self-balance하도록 한다.

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
트리에 대해 volumes을 쿼리하는 것은 매우 효율직이다, AABB에 대한 충돌 체크가 빠른 한. Sphere, AABB , raycasts 모두 매우 빠르다.

그 트리를 쿼리하는 것은 트리에 있는 각 노드와 충돌을 탐지하는 것을 포함한다. 이것은 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안에 위치된다 (그리고 그들은 contact constraints를 함꼐 가진 어떤 오브젝트들도). 이것은 왜냐하며 자고있는 오브젝트들은 새로운 islands를 형성할 때 전혀 고려될 필요가 없기 대문이다.  그들이 잠들었기 때문이다. 이것을 알아서, 한 작은 flat가 도형 내에서 설정될 수 있다, 그것이 island에 배치될 때. 이 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"라는 오래된 격언이 있다. broadphases에 대해서, 그러나 dynamic AABB tree는 완전히 나를 감명시켰다.

성능 관점에서, 나의 시뮬레이션은 100개 이상의 dynamic bodies에서 N^2 broadphase로 중단되고 병목현상을 겪을 것이다. 이제 나는 시뮬레이션 시간의 약 5%를 차지하는 broadphase로 약 5000개의 rigid bodies를 시뮬레이션할 수 있다. 나의 현재 bottleneck은 constraint solving동안의 cache misses이다.