Нахождение общего объема двух перекрывающихся кубоидов

Question

Какой самый эффективный способ найти общее пространство, занимаемое двумя перекрывающимися объектами куба?

Я не обязательно ищу исходный код, просто общее представление о том, как он должен решаться.

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

Answer 1

Перекрытие двух не повернутых кубов все еще остается «коробкой». Если две угловые точки поля A являются (x, y, z) и (x ', y', z ') (x'> x, y '> y, z'> z), и две угловые точки поля B имеют вид (a, b, c) и (a ', b', c ') (a'> a, b '> b, c'> c) тогда объем перекрытия равен

max(min(a',x')-max(a,x),0)
* max(min(b',y')-max(b,y),0)
* max(min(c',z')-max(c,z),0)

Как читать формулу:

Перекрытие начинается на оси X в максимуме двух координат x и a и заканчивается в минимуме a 'и x'. Если a ' min (a', x ') = a', поэтому разница становится отрицательным, а объем равен нулю (отсюда и внешний максимум (..., 0)) То же самое относится и к двум другим осям.

Answer 2

Если кубы не повернуты (выровнены по оси), перекрытия размеров достаточно, чтобы описать перекрытие кубов.

Рассмотрим проблему в двух измерениях:

      ________
     |    S2  |
 ____|___     |
|    |   |    |
|    |___|____|
| S1     |
|________|

Область перекрытия описывается шириной S1.xmax - S2.xmin и высотой S1.ymax - S2.ymin. Для определения порядка вычитания требуется пара if тестов. Вы можете обнаружить, что нет никакого совпадения вообще. Чтобы сделать это для кубов, рассмотрите размерность z в дополнение к x и y.

Answer 3

Вычислите мин / макс в каждом измерении каждого из ваших кубов, а затем проверьте их друг против друга, например, в направлении х, где кубы помечены 1 и 2

XminInt;
if ( Xmin1 > Xmax2 )
{
    // no intersection
}
else if ( Xmin1 >= Xmin2 )
{
    // possible cube intersection
    XminInt = Xmin1;
}
else if ( Xmin2 <= Xmax1 )
{
    // possible cube intersection
    XminInt = Xmin2;
}

Сделайте что-то подобное длямакс и повторите как для у и г.Если вы нажмете на случай отсутствия пересечения в любом из них, вы можете выйти рано.Если вы не выйдете досрочно ни в одном из шести возможных условий досрочного выхода, то у вас будут все шесть определяющих значений для куба пересечения, т. Е. Мин / макс для каждого измерения.Простейшим примером является метод разделяющая ось .Поскольку ваши фигуры представляют собой кубы и выровнены по осям, декартовы оси являются возможными разделяющими осями.Тестирование - это просто сравнение значений min / max, как указано выше.

Обратите внимание, что я реализовал описанный выше метод в C ++ и подтвердил, что он работает.