Я работаю над чисто непрерывным физическим движком, и мне нужно выбрать алгоритмы для широкого и узкого обнаружения фазовых столкновений. «Чисто непрерывный» означает, что я никогда не выполняю тесты пересечений, а вместо этого хочу найти способы отловить каждое столкновение до того, как оно произойдет, и поместить каждое в стек «запланированных столкновений», который заказывается TOI.

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

Я понятия не имею, какие непрерывные аналоги могут существовать для сегодняшних дискретных методов отбора столкновений, таких как четырехугольники. Как я могу предотвратить неуместные и бессмысленные широкие тесты, такие как дискретный движок? Я также хотел бы видеть столкновения более чем на 1 кадр впереди.

Узкая фаза
Мне удалось адаптировать узкий SAT к непрерывной проверке, а не к дискретным, но я уверен, что есть и другие лучшие алгоритмы в статьях или сайтах, которые вы, ребята, могли встретить.
Какой быстрый или точный алгоритм вы предлагаете мне использовать и каковы преимущества / недостатки каждого из них?

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

Я действительно просто бросаю идеи здесь. Предполагая, что у вас есть (по крайней мере) currentположение и nextположение; за каждый кадр.

Вам понадобятся две отдельные широкие фазы, за которыми следует ваша узкая фаза:

• Тот, который выясняет, что столкновение произойдет.
• Тот, который приблизительно определяет, где на самом деле происходит столкновение (например, широкая фаза / неточный SAT)
• Наконец, ваша узкая фаза улучшит результат второй широкой фазы.

Начальная широкая фаза

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

Вторая широкая фаза

Сделайте двоичный мультисэмпл, используя метод пересечения окружности, который вы описали. Другими словами:

left = current
right = next
midpoint = (left + right) / 2
loop a desired amount of times tweaked to the accuracy you want:
  is a collision occuring at midpoint?
    right = midpoint
  else?
    left = midpoint
  midpoint = (left + right) / 2
pointOfCollision = midpoint

Эта настройка точности также может учитывать расстояние - я думаю, что использование «квадрата длины» next - currentдаст идеальный результат с точки зрения пикселей.

Узкая фаза

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

в заключение

Вы сможете отработать время-пересечения с pointOfCollision, currentи вашим текущим speedи acceleration(если у вас есть разумный интегратора).

Хорошо, я видел, что вы обновили свой вопрос, чтобы быть более конкретным. Я постараюсь помочь вам еще немного.

Для вашей первой проверки широкой фазы я настоятельно рекомендую пространственное хеширование .

По сути, вы делите свой экран на сетки одинакового размера. Затем, если объект находится в сетке, вы добавляете его в «корзину» в 1-мерной хеш-таблице.

Это ваша первая проверка сделана. Если объекты не находятся в одном и том же сегменте, они не смогут пересекаться.

Продолжая с этим, теперь у вас есть список блоков с объектами (потенциально) в них. Вы можете сделать еще одну проверку широкой фазы здесь:

A.) Разделить этот сегмент на 4 других блока и проверить полученную 1-мерную хеш-таблицу. Если они не в одном ведре, столкновения нет.

Или:

B.) Выполнение простой проверки расстояния с учетом ширины и / или высоты объекта для обеспечения точности.

Но как насчет того, когда вы потенциально можете столкнуться?

Тогда я бы порекомендовал что-то вроде этого . По сути, это своего рода смесь полигональных столкновений (для сложных фигур) или прямоугольника / круга для менее сложных фигур.

Кроме того, если вы действительно хотите «отловить коллизии до того, как они произойдут, и сохранить их», вы всегда можете сделать что-то вроде этого:

Если два объекта находятся в одном ведре, они могут столкнуться.

Кроме того, достаточно ли близки объекты, чтобы они могли скоро столкнуться? (С учетом скорости, размера объекта и расстояния)

Если ответ на оба вопроса - «да», тогда сохраните его, чтобы выполнить тест пересечения позже.

« Старый ответ

Ну, к сожалению, я потерял след из своего руководства «Все типы столкновений и для чего они используются». :)

Однако, хотя это чрезвычайно широкий квест, я начну с вас.

Там хороший (ответил) вопрос , касающийся чего - то , как это здесь .

А также статья людей, которые сделали N и N + здесь .

Не говоря уже о том, что у вас есть хороший запасной вариант Per-pixel Collision .

Я искренне сомневаюсь, что у кого-нибудь будет удобный список всех типов столкновений, но это должно помочь вам начать.

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