РЕДАКТИРОВАТЬ / ОБНОВИТЬ: Мой самый большой вопрос прямо сейчас заключается в том, является ли уравнение «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 не является жизненно важным, но он может повысить производительность (ИЛИ это может потребовать больше процессорного времени, чем экономит).
Все другие комментарии, предложения или критика приветствуются. Спасибо за помощь!
источник
Ответы:
По сути, вы создали несколько увлеченную версию развернутых томов .
Займите две позиции объекта. «Смести» объект от его начала до конца. Для сферы это создаст капсулу. Для бокса это создаст шестиугольник (или более длинный бокс - это движение вдоль одной оси). Для общих выпуклых многоугольников это создаст другой выпуклый многоугольник.
Теперь вы можете выполнять тесты пересечений (в том числе запросы дерева квадрантов), используя этот развернутый том. Вы можете рассчитать, когда произошло столкновение, перекатить симуляцию с момента начала до времени столкновения и повторить.
Другой вариант, несколько более простой, состоит в том, чтобы сделать то, что указано в @ ashes999, и просто использовать меньший интервал времени или меньшие скорости. Существует идеальная максимальная скорость, полученная из интервала, в котором ни один объект не может двигаться дальше своей самой узкой стороны за одно физическое взаимодействие. Для особенно маленьких или особенно быстрых объектов вы не сможете найти достаточно маленький интервал, который хорошо работает.
См. Обнаружение столкновений в режиме реального времени для одной из лучших вводных / промежуточных книг по теме обнаружения столкновений.
источник
Алгоритм, предложенный в вопросе, прекрасно работает: он быстрый и абсолютно точный , даже когда объекты движутся с предельной скоростью. У меня реализовано квадродерево, поэтому после ввода блоков из шага 1 в квадродерево я обнаружил, что шаг 2 не нужен: моя программа работала почти так же быстро, как и раньше.
Я использую этот алгоритм в течение нескольких месяцев, и он, кажется, совершенно точно определяет время столкновения. Поскольку в Интернете нет ничего лучше, я настоятельно рекомендую использовать это. (Некоторые из ответов в других ответах и комментариях выше отличные, но они либо не совсем соответствуют потребностям, указанным в вопросе, либо автор был очень неоднозначен в отношении чего-либо и никогда не возвращался, чтобы ответить на вопрос о неоднозначности ).
источник
У меня пока недостаточно репутации, чтобы комментировать, но я просто хотел бы добавить, что использование того, что Шон Миддледич упомянул выше, позволяет вычислить ваш «т». По крайней мере, если я понял его ответ, и вы правильно задаете вопрос.
Вот ссылка на удивительный ответ Сэма Хоцевара, который дает лучшее объяснение о нем, которое я когда-либо нашел (он тоже рисовал картинки, ура!)
/gamedev//a/55991/112940
Я не могу сказать, что это быстрее, чем ваш собственный метод, но он, безусловно, даст вам все необходимое для его реализации и сравнения с вашим.
Чтобы не оставлять «ответ только по ссылке», я кратко изложу его идею:
источник