ПрограммированиеТерминыФизика

Sweep And Prune

Используйте данный метод, когда когерентность сцены большая, т.е. когда перемещение объектов происходит нечасто.

Идея определения пересечения AABB vs AABB основана на сортировке и обновлении интервалов в real time. Пусть задано n интервалов Ii = [bi, ei], где 1 <= i <= n. Задача состоит в том, что бы эффективно найти все пересекающиеся пары интервалов. Ii и Ij пересекаются только в том случае, если bj <= ei и bi <= ej. Самое просто решение для проверки всех пар интервалов имеет сложность O(n*n). Более эффективный подход использует sweep алгоритм:
  1. Сортируем все конечные точки интервала по возрастанию.
  2. Для всех интервалов в зависимости от типа точки обновляем (если начальная точка интервала – добавляем, иначе удаляем) множество A, которое содержит пересекающиеся интервалы.

terms | Sweep And Prune

  1. b3, нету никаких пересечений, поскольку A пустое. Обновляем A = {I3}.
  2. b1, пересечение I3 и I1. Обновляем A = {I3, I1}.
  3. b2, пересечение I3 и I2, и I1 и I2. Обновляем A = {I3, I1, I2}.
  4. e3, удаляем I3 из множества A. A = {I1, I2}
  5. e1, удаляем I1 из множества A. A = {I2}
  6. e2, удаляем I1 из множества A. A = {}

В 2d, например, для прямоугольников необходимо проверить пересечение интервалов по двум осям.

Рассмотрим в 3d пересечение AABB vs AABB.

AABB задан как min, max.

Для каждого прохода алгоритма выбирается ось, вдоль которой будет проходить сортировка. Зная ось, указатели на AABB сортируются в возрастающем порядке по min значению. После того как массив отсортирован, проверяем на непересекающиеся AABB, т.е. проверяем AABBj.min[SORT_AXIS] > AABBi.max[SORT_AXIS], если истина, то остальные n-j проверять не надо.

В таком случае можно достигнуть сложности в O(n log n) или в O(kn), в зависимости от сортировки.

Как выбирать ось, вдоль которой сортировать. Например, можно посчитать дисперсию (min+max)/2 AABB. И в зависимости от значения выбирать нужную ось. Но даже в таком случае возможен случай в O(n*n).

Код:

int SORT_AXIS = 0;

struct AABB
{
  Point min;
  Point max;
};

int cmpAABB(const void * a, const void * b)
{
  float mina = (*(AABB**)a)->min[SORT_AXIS];
  float minb = (*(AABB**)b)->min[SORT_AXIS];
  if(mina < minb) return -1;
  if(mina >= minb) return 1;
  return 0;
}

AABB * vAABB[N];

void SweepAndPrune()
{
  //Первая часть алгоритма: сортируем по оси SORT_AXIS
  qsort(vAABB, N, sizeof(vAABB*), cmpAABB);

  //Суммы для подсчета среднеквадратического.
  Point s (0,0,0); 
  Point s2 (0,0,0);

  //Ищем пересекающиеся интервалы.
  for (int i = 0; i < N; ++i)
  {
    AABB * aabb = vAABB[i];

    /*
    Дисперсию будем считать относительно среднего min, max. 
    Можно выбрать какую – то другую характеристику для подсчета.
    */

    Point p = (aabb->min + aabb->max) * 0.5;

    s+=p;
    s2+=p*p;

    for (int j = i + 1; j < N; ++j)
    {
      if (vAABB[j]->min[SORT_AXIS] > aabb->max[SORT_AXIS] )
      break;

      if(AABBOverlap(vAABB[j], aabb))
      {
        /*
        Проверяем коллизии сложных объектов, или какие то другие полезные действия
        */
      }
    }
  }

  //Считаем выборочную дисперсию, и в зависимости от значения выбираем ось.
  v = s2 / N – pow(s / N, 2);
  SORT_AXIS = 0;
  if ( v[1] > v[0] ) SORT_AXIS = 1;
  if ( v[2] > v[SORT_AXIS] ) SORT_AXIS = 2;
}

Что такое Sweep And Prune?

#collision detection

30 августа 2007 (Обновление: 16 фев 2012)

Комментарии [4]