Задать вопрос
Manolito
@Manolito

Как найти все точки проникновения/контакта двух боксов (прямоугольных параллелепипедов), зная координаты их вершин?

У нас есть два бокса (прямоугольные параллелепипеды), мы знаем координаты их вершин. Нам надо определить точки их контакта/взаимопроникновения друг в друга. Кто-нибудь может мне помочь?
P.S. Пишу небольшой физический движок. Такие советы как "используй уже готовый движок" прошу не писать.
  • Вопрос задан
  • 3345 просмотров
Подписаться 2 Оценить Комментировать
Решения вопроса 1
SHVV
@SHVV
Думаю, вам стоит взять готовый опенсорсный движок и посмотреть, как опытные люди это делают.

За основу всех более-менее сложных алгоритмов поиска пересечения выпуклых многогранников берётся "Теорема о разделяющей оси". Суть проста: если проекции многогранников на какую-нибудь прямую не пересекаются, то они не пересекаются в пространстве. Если такой оси нет, то пересекаются. Как таковых конечных точек пересечения у них при этом не будет, будет целый многогранник этих пересечений. Но для физического движка нужно выделить некоторое количество характерных точек и этот выбор будет зависеть от той оси, которую вы сами выберете. В большинстве случаев такой осью выбирают прямую, на которой пересечение проекций минимально.

Какие оси надо проверять? Ведь их бесконечное количество.
Это зависит от топологии. В общем случае достаточно проверять оси коллениарные нормалям всех граней многогранников (в этом случае мы ищем пересечение с гранью), и оси полученные векторным произведением каждого ребра одного многогранника с каждым ребром другого (пересечение ребро - ребро). Но, так как у Бокса очень много параллельниых граней и рёбер, то все их проверять нет смысла. Так как получится куча одинаковых осей.
Итого получается, что нужно проверить 3 + 3 (грани) + 3 * 3 (пары рёбер) = 15 потенциальных разделяющих осей. В первом случае, необходимо потом будет найти пересечение грани с вершинами, и из тех вершин, что пересекают плоскость построить многоугольник и пересечь его уже в 2Д, получив от 1-й до 6-ти точек пересечения. Во втором случае ещё проще - ищем точку пересечения двух векторов.

ПС: Лучше начинать собственный движок с более простых фигур - сфер и касюлей. У них функция пересечения на пару порядков проще.
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 1
Able1991
@Able1991
Пишу на рельсах
пары в универе не надо было прогуливать)
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы