С чего начать инкапсуляцию трехмерной сетки в иерархии ограничивающих объемов

Question

Я работаю над довольно элементарным симулятором физики твердого тела для моих исследований.Мне нужно очень детальное обнаружение столкновения.То есть мне требуется точка соприкосновения XYZ полигонов ячеек.Я не могу просто заключить сетки в грубые ограничивающие объемы и основывать свои ответы на столкновения на них.

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

В настоящее время я читаю «Обнаружение столкновений в реальном времени» Эриксона, что весьма полезно, но мне интересно, знает ли кто-нибудь какие-либо книги / документы, которые конкретно касаются этой проблемы.на генерации AABB из полигонов.Каждый кадр при обходе BVH я бы преобразовывал AABB с помощью матрицы преобразования твердого тела, создавая OABB.Тогда я бы проверил OABB на пересечение.Я еще не реализовал это, и в настоящее время это все теоретическое дело.Если у кого-то есть опыт в этом, любые советы или более эффективные алгоритмы будут с благодарностью!

Answer 1

Вы можете реализовать кэширование треугольников, что является очень простой техникой. По сути, вы сохраняете пару листовых узлов из двух BVH, которые сталкиваются. В следующий раз, когда вы проверите коллизию между этими двумя BVH, начните с немедленного тестирования сохраненных двух конечных узлов. Если когерентность между кадрами высока, как это обычно бывает в играх, то есть вероятность, что вы обнаружите столкновение, даже не проверяя две BVH!

UNHC gamma опубликовала несколько работ, в которых упоминается / описывается кэширование треугольников. Например, см. этот документ (я думаю, что он очень удобочитаемый!).

Answer 2

Одним из факторов, способствующих повышению производительности, является использование методов линейного программирования для оптимальности и уменьшения точки.Одним из таких решателей является GJK или Gilbert, Johnson Keerthi solver.

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