Найдите AABB из множества трехмерных плоскостей, которые образуют выпуклый корпус

Question

У меня есть информация о 3D-самолетах. Когда все самолеты объединятся, он сформирует трехмерный выпуклый корпус.

Вот пример ввода.
Каждая трехмерная плоскость обозначается точкой на плоскости и ее нормалью.
Все нормали указывают внутрь: -

- (-1,0,0)              with normal = (1,0,0)
- ( 1,0,0)              with normal = (-1,0,0)
- (0,-1,0)              with normal = (0,1,0)
- (0,1,0)               with normal = (0,-1,0)
- (0,0,-1)              with normal = (0,0,1)
- (0,0,1)               with normal = (0,0,-1)
- (0.142,-7.18,10.12)   with normal = (0.001,0.31,-0.95) 
- note: some planars can be redundant (contribute nothing) e.g. the last one

Вопрос: Как рассчитать AABB из него?
Решение из приведенного выше примера: ((-1,-1,-1),(1,1,1)).

(Сначала я хочу центр масс, но я понял, , что это трудная проблема .
AABB должен быть достаточно хорош для меня. )

Мое плохое решение - найти все вершины корпуса, используя Конструктивная геометрия твердого тела , затем выполнить MIN & MAX для них, но производительность слишком плохая.

В реальном случае я хочу найти центральную точку трехмерного корпуса, когда два выпуклых корпуса перекрываются.
Эта информация может быть полезна для более точного ответа на столкновения в Physics Engine.

Answer 1

Это классическая проблема линейного программирования. Учитывая набор линейных неравенств (представленных плоскостями в вашем случае, скажем ax + by + cz + d> = 0) и линейную функцию (скажем, f (x, y) , z) = x), найдите точку, которая минимизирует функцию при выполнении всех неравенств. AABB является решением 6 таких задач для функций x, -x, y, -y, z и -z.

Существует несколько методов решения этой проблемы, наиболее известным из которых является симплекс-алгоритм и множество готовых библиотек (включая библиотеки, использующие графические процессоры).