Cube on Cube алгоритм обнаружения столкновений?

Question

Я пытаюсь найти наиболее эффективный способ проверить, сталкиваются ли 2 куба произвольного размера друг с другом. Стороны кубов не обязательно все равны по длине (возможна коробка). Учитывая эти ограничения, как я могу эффективно проверить, сталкиваются ли они? (каждая коробка имеет 24 вершины) Спасибо

Они выровнены по оси

Answer 1

Поскольку оба поля выровнены по оси, вы можете просто сравнить их экстенты:

  return (a.max_x() >= b.min_x() and a.min_x() <= b.max_x())
     and (a.max_y() >= b.min_y() and a.min_y() <= b.max_y())
     and (a.max_z() >= b.min_z() and a.min_z() <= b.max_z())

Answer 2

Для логического запроса используйте ответ Лоуренса. Его также можно настроить для работы с движущимися прямоугольниками, но тогда вам нужно использовать двоичный поиск, чтобы найти точку пересечения или временной интервал.

Решение параметрического времени для пересечения по оси

Другое решение, если вам нужны подвижные боксы, - это найти параметрическое время, когда пересечение происходит по каждой оси отдельно, относительно направления движения. Давайте назовем поля А и В, их крайние точки для Мин и Макс. Вам нужно только одно направление, потому что вы можете вычесть направление A из направления B и остаться с одним вектором. Таким образом, вы можете считать B движущимся, а A неподвижным. Назовем направление D. Решение для t дает:

(для начала пересечения по D)
Bmax + TEnter D = Амин
tEnter D = Амин - Bmax
tEnter = (Amin - Bmax) / D

(для конца пересечения вдоль D; задняя сторона A)
Bmin + tLeave D = Amax
tLeave D = Amax - Bmin
tLeave = (Amax - Bmin) / D

Сделайте эту проверку на каждой оси, и если они все перекрываются, у вас есть пересечение. Если знаменатель равен нулю, у вас есть бесконечное перекрытие или нет перекрытия по этой оси. Если tEnter больше 1 или tLeave меньше нуля, то перекрытие происходит дальше, чем длины направления, или в неправильном направлении.

bool IntersectAxis(float min1, float max1, float min2, float max2,
    float diraxis, float& tEnter, float& tLeave)
{
    const float intrEps = 1e-9;

    /* Carefully check for diraxis==0 using an epsilon. */
    if( std::fabs(diraxis) < intrEps ){
        if((min1 >= max2) || (max1 <= min2)){
            /* No movement in the axis, and they don't overlap,
                hence no intersection. */
            return false;
        } else {
            /* Stationary in the axis, with overlap at t=0 to t=1 */
            return true;
        }
    } else {
        float start = (min1 - max2) / diraxis;
        float leave = (max1 - min2) / diraxis;

        /* Swap to make sure our intervals are correct */
        if(start > leave)
            std::swap(start,leave);

        if(start > tEnter)
            tEnter = start;
        if(leave < tLeave)
            tLeave = leave; 
        if(tEnter > tLeave)
            return false;
    }
    return true;
}

bool Intersect(const AABB& b1, const AABB& b2, Vector3 dir, float& tEnter, float&         tLeave)
{
    tEnter = 0.0f;
    tLeave = 1.0f;

    if(IntersectAxis(b1.bmin.x, b1.bmax.x, b2.bmin.x, b2.bmax.x, dir.x, tEnter, tLeave) == false)
        return false;
    else if(IntersectAxis(b1.bmin.y, b1.bmax.y, b2.bmin.y, b2.bmax.y, dir.y, tEnter, tLeave) == false)
        return false;
    else if(IntersectAxis(b1.bmin.z, b1.bmax.z, b2.bmin.z, b2.bmax.z, dir.z, tEnter, tLeave) == false)
        return false;
    else
    return true;
}