Используйте данный метод, когда когерентность сцены большая, т.е. когда перемещение объектов происходит нечасто.
Идея определения пересечения 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, которое содержит пересекающиеся интервалы.
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(constvoid * a, constvoid * b)
{
float mina = (*(AABB**)a)->min[SORT_AXIS];
float minb = (*(AABB**)b)->min[SORT_AXIS];
if(mina < minb)return -1;
if(mina >= minb)return1;
return0;
}
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;
}