Небольшие, высокоскоростные столкновения объектов: избегание туннелирования

14

РЕДАКТИРОВАТЬ / ОБНОВИТЬ: Мой самый большой вопрос прямо сейчас заключается в том, является ли уравнение «t ​​= ...» шага 3 хорошей идеей или есть лучший способ сделать это. Большинство других проблем были частично или полностью решены, но никаких комментариев или ответов по этому вопросу не было. Опять же, аналитическое решение, вероятно, требуется, скорости и расстояния слишком велики, а объекты слишком малы, для любого итеративного / рекурсивного решения (некоторые из них предлагаются ниже в комментариях), о которых я могу думать (хотя, если есть специальное итеративное / рекурсивное решение, которое отлично справится с подобными ситуациями, тогда я определенно открыт для него). Большое спасибо за вашу помощь, вы все замечательные, и я очень ценю ваши мысли и помощь!

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

Приведение лучей не будет работать, так как это обнаружение столкновения между двумя высокоскоростными объектами, а не между одним объектом и неподвижной стеной. (Если только я не правильно понял, что такое кастинг лучей?) Производительность ОЧЕНЬ важна; если это вообще возможно, я хочу избежать значительного снижения производительности. У меня уже есть функциональное и очень эффективное quadtree ( http://en.wikipedia.org/wiki/Quadtree ), поэтому я изменю и использую его, как описано ниже.

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

ПРЕДЛОЖЕННОЕ РЕШЕНИЕ:

Шаг 1:

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

Шаг 2: (возможно, хотите пропустить этот шаг?)

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

РЕДАКТИРОВАТЬ: ниже, Шон Middleditch предложил использовать развернутые объемы / пересечение капсул (если объекты являются кругами). Это оставляет три варианта: 1) полностью пропустить шаг 2. 2) Сделайте шаг 2 по-моему. 3) Сделай так, как Шон. Путь Шона будет в вычислительном отношении более дорогим, чем моя идея, но он отсеет больше ложных срабатываний, чем мой, и не позволит им добраться до последнего шага.

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

Шаг 3:

Используйте приведенное ниже уравнение t =, если дискриминант (т. Е. Часть под квадратным корнем) отрицателен или равен 0, столкновений нет, если положительный, тогда используйте значение t в качестве времени столкновения (после которого легко соответствующим образом настроить положения. ..если оба объекта продолжают существовать после столкновения). Уравнение:

t = (-1/2 sqrt ((2 a w-2 a x + 2 b y-2 b z-2 c w + 2 c x-2 d y + 2 dz) ^ 2-4 (w ^ 2- 2 w x + x ^ 2 + y ^ 2-2 y z + z ^ 2) (a ^ 2-2 a c + b ^ 2-2 b d + c ^ 2 + d ^ 2-r ^ 2-2 r ss ^ 2)) - a w + a xb y + b z + c wc x + d yd z) / (w ^ 2-2 w x + x ^ 2 + y ^ 2-2 y z + z ^ 2 ) .

Где (1 и 2 используются для обозначения объектов 1 и 2):

t - отрицательное значение времени между 0 и -1, где 0 - текущий кадр, а -1 - предыдущий кадр;

а = х позиция 1;

b = y позиция 1;

с = х положение 2;

d = y позиция 2;

w = x скорость 1;

х = х скорость 2;

у = у скорость 1;

z = у скорость 2;

r = радиус 1;

s = радиус 2;

Вывод: (^ 2 означает квадрат)

Возьмите параметрические уравнения (например, newxpos1 = a + t w) для движений объектов и включите их в формулу расстояния (возводя в квадрат обе стороны): квадрат формулы расстояния = (a + t w - (c + t x)) ^ 2 + (b + t y - (d + t * z)) ^ 2. Помните, что это будет отрицательным. Чтобы найти время столкновения для двух круглых объектов, мы устанавливаем левую сторону равной (r + s) ^ 2. Решая для t, используя квадратное уравнение (и много очень утомительной алгебры), мы получаем вышеупомянутое уравнение "t = ...".

Мои вопросы:

1) Это хороший способ сделать это? Будет ли это работать вообще? Собираюсь ли я столкнуться с непредвиденными проблемами? (Я знаю, что у меня будут проблемы, когда сталкиваются более двух объектов одновременно, но мне все равно, поскольку единственный случай, на который я действительно возражаю, это когда они имеют низкие относительные скорости (если относительные скорости высоки тогда «глупое» решение, которое дает алгоритм, будет «достаточно хорошим», и человек не сможет увидеть ошибку), и если более 2 столкнутся с низкими относительными скоростями за один и тот же временной шаг, большинство решений будет быть достаточно близким в любом случае, так как я не планирую иметь кучу неупругих столкновений)

2) Мое выступление сильно пострадает? Я не думаю, что это будет, но если это произойдет, есть ли лучший способ сделать это?

3) Должен ли я пропустить шаг 2 и сразу перейти от шага 1 к 3? Очевидно, что шаг 2 не является жизненно важным, но он может повысить производительность (ИЛИ это может потребовать больше процессорного времени, чем экономит).

Все другие комментарии, предложения или критика приветствуются. Спасибо за помощь!

MindSeeker
источник
1
Кристер Эриксон (Christer Ericson) имеет некоторую информацию о проверке сферы / сферы в своей оранжевой книге. Есть немало способов решить проблему, но я думаю, что вам больше всего понравится интервал, уменьшающийся вдвое. Это хорошо, чтобы попытаться получить этот материал самостоятельно, но вы действительно должны просто посмотреть на оранжевую книгу и сравнить, чтобы получить действительно хорошую процедуру обнаружения и узнать больше.
RandyGaul
Похоже, у вас уже есть план ... попробуйте и посмотрите, как он работает?
Тревор Пауэлл,
Я думаю, что «обычный» способ состоит в том, чтобы иметь небольшой максимальный интервал времени дельты. Поэтому, если у вас есть 1000 мс, просто смоделируйте 10x 100 мс (или 100x 10 мс, или 33x 30 мс, или что-то подобное).
ashes999
@RandyGaul Я просмотрел алгоритм, описанный на стр. 215-218, особенно на стр. 218 (предварительный просмотр Google). Это довольно элегантно, хотя я еще не продумал все его значения, сильные и слабые стороны. Это будет намного быстрее, чем у меня? Если так, то какая часть моего алгоритма медленная по сравнению с рекурсией Эриксона? Будет ли уравнение на шаге 3 слишком медленным? Эта рекурсия заставляет меня сомневаться, поскольку некоторые объекты могут двигаться ОЧЕНЬ быстро, и поэтому в некоторых случаях может потребоваться большая рекурсия. (Кроме того, ОЙ, 70 долларов за эту книгу ...)
MindSeeker
1
@MindSeeker У меня нет времени, чтобы просмотреть ваш вывод, но я уверен, что алгоритмы в книге Эриксона, любой из них, будут работать очень хорошо и, вероятно, будут быстрее и надежнее, чем ваши вещи. Вы можете найти PDF версии онлайн бесплатно, если вы хотите продемонстрировать другие страницы. Кроме того, если вы собираетесь часто обнаруживать столкновения, оранжевая книга является одним из основных продуктов.
RandyGaul

Ответы:

9

По сути, вы создали несколько увлеченную версию развернутых томов .

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

Теперь вы можете выполнять тесты пересечений (в том числе запросы дерева квадрантов), используя этот развернутый том. Вы можете рассчитать, когда произошло столкновение, перекатить симуляцию с момента начала до времени столкновения и повторить.

Другой вариант, несколько более простой, состоит в том, чтобы сделать то, что указано в @ ashes999, и просто использовать меньший интервал времени или меньшие скорости. Существует идеальная максимальная скорость, полученная из интервала, в котором ни один объект не может двигаться дальше своей самой узкой стороны за одно физическое взаимодействие. Для особенно маленьких или особенно быстрых объектов вы не сможете найти достаточно маленький интервал, который хорошо работает.

См. Обнаружение столкновений в режиме реального времени для одной из лучших вводных / промежуточных книг по теме обнаружения столкновений.

Шон Миддледич
источник
Спасибо за потрясающий вклад! Разбив ваш ответ, я могу задавать вопросы об этом: «Смести объект с начала до конца». Пока я отслеживаю; безусловно, улучшение по сравнению с моим методом коробки. Я передам эти фигуры квадродереву, а затем проверю более точные коллизии. «Вы можете рассчитать, когда произошло столкновение». Ха-ха, легче сказать, чем сделать :) Вы рекомендуете, чтобы я придерживался своего уравнения из шага 3 для шага? Или есть лучший способ? Это действительно важная часть.
MindSeeker
[продолжение] «Еще один вариант ...» Я думал об этом варианте, но, к сожалению, скорость слишком высока. Смотрите мой комментарий к @ ashes999 и отредактируйте выше для получения дополнительной информации. Большое спасибо за Вашу помощь!
MindSeeker
Единственный способ узнать о производительности - это попробовать, измерить и посмотреть. Ранее я видел «явно» неэффективный код, который значительно превосходил эффективные версии, обычно по неинтуитивным причинам. Не спрашивайте, что быстрее; проверить и выяснить.
Шон Миддледич
Справедливо, я попробую свой метод, модифицированный, как вы предложили. Мой вопрос в комментарии все еще остается: «Вы можете рассчитать, когда произошло столкновение». Вы рекомендуете, чтобы я придерживался своего уравнения из шага 3 для этого шага? Или есть лучший способ? Это самая сложная часть проблемы, я думаю. Простые тома, если я их правильно понимаю, могут сказать мне, что пути объектов пересекаются, но не могут сказать мне, если / когда сами объекты сталкиваются.
MindSeeker
1
@MindSeeker Swept геометрия - это лучевое вещание, за исключением того, что вы применяете форму вместо луча. Таким образом, метод должен выглядеть аналогично использованию приведения лучей с «лучами» для всех быстро движущихся объектов вместо одного луча против неподвижного объекта. После того, как вы определили потенциальные столкновения от «лучей», вам нужно разрешить время для обоих «лучей», чтобы убедиться, что они были в одном и том же месте в одно и то же время.
каменный металл
2

Алгоритм, предложенный в вопросе, прекрасно работает: он быстрый и абсолютно точный , даже когда объекты движутся с предельной скоростью. У меня реализовано квадродерево, поэтому после ввода блоков из шага 1 в квадродерево я обнаружил, что шаг 2 не нужен: моя программа работала почти так же быстро, как и раньше.

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

оборота MindSeeker
источник
1

У меня пока недостаточно репутации, чтобы комментировать, но я просто хотел бы добавить, что использование того, что Шон Миддледич упомянул выше, позволяет вычислить ваш «т». По крайней мере, если я понял его ответ, и вы правильно задаете вопрос.

Вот ссылка на удивительный ответ Сэма Хоцевара, который дает лучшее объяснение о нем, которое я когда-либо нашел (он тоже рисовал картинки, ура!)

/gamedev//a/55991/112940

Я не могу сказать, что это быстрее, чем ваш собственный метод, но он, безусловно, даст вам все необходимое для его реализации и сравнения с вашим.

Чтобы не оставлять «ответ только по ссылке», я кратко изложу его идею:

  1. рассчитать разницу Минковского между двумя ограничивающими прямоугольниками
  2. используя относительную скорость между ними, приведите отрезок луча / линии от начала координат до прямоугольника, созданного разностью Минковского, чтобы получить точку пересечения
  3. Если луч достигнет, разделите расстояние, на которое прошел ваш луч, на длину вектора, представляющего относительную скорость, и вы получите «т»
  4. нажмите на ссылку, которую я предоставил выше, и увидите самое красивое объяснение всего этого с множеством картинок. Это превосходно.
оборота user1593842
источник