Понимаю, что не совсем в тему форума, но может кто знает по сабжу. На геймдеве мне толком ничего не посоветовали. Вообщем есть два ориентированных в пространстве бокса (каждый задаётся точкой в пространстве, ориентацией, и размерами в ЛСК). Надо очень быстро посчитать минимальный, объединяющий их бокс.
Что же ни у кого нет мыслей? Например в книге Девида Эберли -"3D Game Engine Design", описан для не пересекающихся боксов такой: Находим центр нового, интерполяцией центров двух входных. Для вычисления ориентации, переводим матрицы боксов в кватернионы, складываем, нормализуем. А для поиска размеров, проецируем все 16 точек боксов, на оси нового бокса. Только этот метод даёт серьезную погрешность, так как расположение осей нового бокса зависит только от осей первоначальных боксов, и не зависит от их положения. Есть мысль найти три бокса такими способами: И есно взять с наименьшим объёмом. Что скажете, гуру A&O?
Задача сродни оптимальной раскройки. Нет однозначного оптимального решения. Несколько лет назад тебе бы посоветовали Генетический Алгоритм. Сейчас я не в кусе что в моде
agrischuk Мне точное решение не нужно. Нужно быстрое и приближенное к правде. Генетические алгоритмы здесь не нужны, точный ориентированный бокс высчитывается за O(N^3) для произвольного облака точек. Есть и пошустрее способы, но есно с погрешностями. Возможно метод предложенный Еберли неплох для определённой системы боксов (например костной иерахии).
Да? Интересно посмотреть как. Сдается мне задача класса нелинейного программирования и в лоб не решается. Ты наверное имеешь ввиду что ориентированый - это ориентированый по осям. Это совсем другой упрощенный случай. Касательно твоей задачи оно не применимо.
Решение должно быть около выше приведеного метода. ИМХО неплохо бы сработало такое: найти угол в одном из даных bb, в котором пересекаються три поверхности и образуют сумарную наибольшою площадь. Через них провести bb. Если такой угол найти нельзя, то найти наибольшую площадь по двум поверхностям. А еще одно измерение взять с другого bb.
agrischuk Да алгоритм впервые предложен Joe O'Rourke's в "Finding Minimal Enclosing Boxes". Смысл в том, что в трёхмерном пространстве, у минимального ориентированного бокса, на двух смежных между собой гранях(с общим ребром), обязательно лежит хотя бы по одному ребру выпуклой оболочки, множества исходных точек. На остальных четырёх гранях, есть как минимум одна точка множества. Можно перебрать все варианты из двух рёбер которые лежат на смежных гранях бокса, построить для каждого варианта свой бокс, и спроецировать точки на его оси. Если же у нас множество точек, а не выпуклая оболочка то сложность как раз O(N^3), так как для выпуклой оболочки надо будет делать меньше переборов. К сожалению этот метод совершенно не подходит для риалтайма. Под "ориентированным" подразумеваю "ориентированный в пространстве", то есть помимо размеров имеющий три вектора ориентации в пространстве. Ты наверно имел ввиду "выровненный по осям". Тут такая терминология: AABB (axis-aligned bounding box). OBB (oriented bounding box)
Ну дык, у тебя же не точки, а два прямоугольных паралелепипеда. Есть мнение, как минимум две смежные грани одного bb и одна точка другого должны лежать на минимальном bb. И того имеем по три комбинации смежных граней для каждого bb, так как остальные грани лежат внутри минимального bb. 1. Найти сумарную площадь для каждой комбинации смежных граней. 2. Взять комбинацию с максимальной площадью. 3. Проверить две поверхности которые проходят через смежные грани на пересечение с другим bb. Если пересечение есть, перейти к шагу 2, взявши следующую комбинацию с макс. площадью. Замечание: сдесь будет не больше 2-х итераций в общем случае. 4. Найти остальные две точки. Одна точка на другом bb (если они не пересекаються). Вторая на первом или на втором, можно найти сравнив наиболее удаленные точки. Надо будет проверить на практике.
agrischuk Получить точки не проблема. Думаю не совсем, например когда расстояние между боксами много больше размеров самих боксов. Но даже если и не больше, то учитывать это всё равно нужно. Думаю что найти и точно и быстро, вряд ли возможно. Но как уже писал, идеально мне не нужно. Мне это нужно для перестройки бинарного дерева ограничивающих объёмов. В основном везде рекомендуют для динамики использовать AABB, так как его перестройка намного дешевле, но в целом его обход для определения пересечений в 2 раза дороже чем с OBB. Нашёл один интересный пейпер, там как раз обновляется динамика, и подход довольно похожий: если расстояние между боксами небольшое, то применяется метод Еберли, а если большое, то за ось берут вектор между центрами боксов. _http://gamma.cs.unc.edu/CAB/publications/
