Что такое хороший алгоритм для обнаружения столкновения между движущимися сферами?

27

Если (с целью обнаружения столкновения) трехмерные объекты представлены в игре сферами, что является хорошим алгоритмом для обнаружения столкновения между сферами?

Если у каждого объекта есть позиция в последнем кадре и новая (желаемая) позиция, то каков хороший алгоритм, который будет определять столкновения, в которых сферы не пересекались в предыдущем кадре, и они могут не пересекаться во втором кадре, но они пересекались где-то посередине?

collision-detection kevin42
источник

Ответы:

18

В основном вы ищете след.

Эта страница, вероятно, поможет вам: http://www.realtimerendering.com/intersections.html

Движущаяся сфера / сфера: (местоположение) Добавьте радиус движущейся сферы к статической сфере и рассматривайте движущуюся сферу как луч. Используйте этот луч для пересечения луча / сферы. Смотри Гомес; Шредер для кода (статья содержит ошибку при выводе, код в порядке); и RTR2, p. 622.

тетрада
источник
1
Это не работает, если обе сферы двигаются (даже если вы делаете это дважды). Мне кажется, что сначала вам нужно будет проверить расстояние между линиями, охватывающими движение a, и одним охватывающим движением b, и если это меньше радиуса a + радиус b, у вас возможное столкновение. После этого я проверил бы, где эта точка находится во времени для сферы a, а где для сферы b, чтобы увидеть, что время близко. Если так, я бы проверил скорость по отношению к расстоянию во времени для этой точки, если это все еще возможное столкновение, я бы пошагово уточнил.
Кадж
15
На самом деле это так, вам просто нужно сделать движение относительным. Поэтому, если обе сферы движутся, вы просто вычитаете скорость одной из сфер из обеих, чтобы у вас была одна «движущаяся» сфера и одна «неподвижная» сфера. Тогда вы можете использовать выше.
Тетрад
8

Используйте тест развертки, как показано в этой статье Gamasutra.

Firas Assaad
источник
4

С верхней части моей головы:

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

И это все, что нужно, я ожидаю, что это будет довольно быстро.

Роберт Массайоли
источник
1

Вот еще одна хорошая статья о Гамасатуре .

Матин Улхак
источник
1
Я понимаю, что это 7 лет спустя, но этот ответ только ссылка. К счастью, ссылка еще жива, но если бы ее не было, ваш ответ ... не был бы ответом.
Draco18s
0

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

ZorbaTHut
источник
Он мог бы сделать игру в пул для всех, кого вы знаете.
Кадж
Если он делал игру в пул, то его «игровому дизайну это абсолютно необходимо» .
deft_code
Вы правы, не изобретайте велосипед . Но только для тренировки это может стоить того.
user712092
4
Я не согласен с прямым унынием в качестве ответа .
Бобобобо
Я согласен с @bobobobo, вопрос не в том, стоит ли это хлопот или нет, будущий пользователь, который видит эту ветку, может абсолютно нуждаться в ответе, независимо от стоимости. Это было бы лучше в качестве комментария.
ТомЦагк
0

На Flipcode есть статья о том, как получить обнаружение столкновений с помощью математики . У него есть круг-круг. Существует способ точно определить точку столкновения и проверить, есть ли столкновение вообще.

user712092
источник
Я понимаю, что это 7 лет спустя, но этот ответ только ссылка. К счастью, ссылка еще жива, но если бы ее не было, ваш ответ ... не был бы ответом.
Draco18s
0

Обнаружение столкновения для движущегося объекта обычно называется «Расчетом охвата объема», вот несколько кодов / статей по этому вопросу.

http://www.gpu-voxels.org/demos/ (Демо)

Библиотеки исходного кода:

https://github.com/fzi-forschungszentrum-informatik/gpu-voxels

https://libigl.github.io/tutorial/#swept-volume

https://github.com/gradientspace/geometry3Sharp

Статьи:

http://gamma.cs.unc.edu/SV/sm03.pdf

https://www.cs.columbia.edu/~allen/PAPERS/abrams.swept.pdf (к сожалению, нет исходного кода)

http://www.realtimerendering.com/intersections.html (довольно большой набор ссылок)

TarmoPikaro
источник
1
Ответы, содержащие только ссылку (или в данном случае несколько), не содержат фактического ответа. Вы должны включить соответствующую информацию в ваше сообщение, чтобы, если эти ссылки не работают, ваше сообщение все еще было понятно.
Draco18s
Информация за ссылками немного лучше объясняет, чем я на данный момент. За ссылками также есть демонстрационные видеоролики, которые дают некоторое представление о том, что происходит в режиме реального времени.
TarmoPikaro
1
meta.stackexchange.com/a/8259/313685
Draco18s