AABB: Axis-Aligned Bounding Box

AABB: Axis-Aligned Bounding Box (ограничивающий параллелепипед выровненный по координатным осям) — это ограниченная область в пространстве в виде прямоугольного параллелепипеда, со сторонами, параллельными осям координат в мировой системе. При вращении объекта AABB изменяет свои размеры, но всегда остается ориентированным по осям координат. Второй вариант AABB — использовать в качестве Bounding Box'а куб со сторонами равными максимальному размеру объекта. Таким образом, в любом положении объект не выйдет за пределы AABB, хотя, конечно, при этом теряется точность.

Существует три представления AABB:

1. min и max координаты вдоль каждой оси.
Это представление определяет AABB как пространство между двумя противолежащими угловыми точками: min и max

AABB = { (x, y, z) | min.x<=x<=max.x, min.y<=y<=max.y, min.z<=z<=max.z }

struct AABB {
    Point min;
    Point max;
};

2. Минимальная угловая точка min и диаметры dx,dy,dz из этого угла:
AABB = {(x, y, z) | min.x<=x<=min.x+dx, min.y<=y<=min.y+dy, min.z<=z<=min.z+dz }

struct AABB {
    Point min;
    float d[3];   
};

3. Последнее представление определяет AABB как центральную точку C и радиусы rx, ry, rz вдоль каждой оси:
AABB = { (x, y, z) | |c.x-x|<=rx, |c.y-y|<=ry, |c.z-z|<=rz }

struct AABB {
    Point c;
    float r[3]; 
};

Проверка на пересечение AABB-AABB:

1. Для первого представления делается тест:

bool TestAABBAABB(AABB a, AABB b)
{
    if (a.max[0] < b.min[0] || a.min[0] > b.max[0]) return false;
    if (a.max[1] < b.min[1] || a.min[1] > b.max[1]) return false;
    if (a.max[2] < b.min[2] || a.min[2] > b.max[2]) return false;
    return true;
}

2. Для второго представления AABB:

bool TestAABBAABB(AABB a, AABB b)
{
    float t;
    if ((t = a.min[0] - b.min[0]) > b.d[0] || -t > a.d[0]) return false;
    if ((t = a.min[1] - b.min[1]) > b.d[1] || -t > a.d[1]) return false;
    if ((t = a.min[2] - b.min[2]) > b.d[2] || -t > a.d[2]) return false;
    return true;
}

3. Наиболее эффективный метод:

bool TestAABBAABB(AABB a, AABB b)
{
    if (Abs(a.c[0] - b.c[0]) > (a.r[0] + b.r[0])) return false;
    if (Abs(a.c[1] - b.c[1]) > (a.r[1] + b.r[1])) return false;
    if (Abs(a.c[2] - b.c[2]) > (a.r[2] + b.r[2])) return false;
    return true;
}

Если данное представление AABB задать как int, то проверку можно переписать таким образом:

overlap = (unsigned int)(B – C) <= (B – A) + (D – C);

В случае C > B, левая часть этого выражения станет inf и overlap = 0.
Поэтому третий тест можно переписать так:

bool TestAABBAABB(AABB a, AABB b)
{
    int r;
    r = a.r[0] + b.r[0]; if ((unsigned int)(a.c[0] - b.c[0] + r) > r + r) return false;
    r = a.r[1] + b.r[1]; if ((unsigned int)(a.c[1] - b.c[1] + r) > r + r) return false;
    r = a.r[2] + b.r[2]; if ((unsigned int)(a.c[2] - b.c[2] + r) > r + r) return false;
    return true;
}

Используется в компьютерной графике для отсечения невидимой геометрии, в физике — для проверки столкновений.

Что такое AABB: Axis-Aligned Bounding Box?

#оптимизация

8 декабря 2005 (Обновление: 24 янв 2011)