Войти
ПрограммированиеФорумФизика

[Challenge] Просчет и оптимизация столкновений в 2D

#0
1:55, 6 дек 2022

  Вобщем, решил поставить себе такое задание: реализовать максимально быстрый(возможно в ущерб используемого обьема памяти) однопоточный софтверный просчет столкновений в 2D до Нового Года.
  Теперь более подробнее. Имеются статичные замкнутые контуры, необязательно выпуклые, также могут быть самопересечения. Нужно очень быстро обрабатывать столкновения таких контуров с подвижными телами, которые тоже в свою очередь могут быть представлены замкнутыми контурами. 
  Есть следующие идеи. Первое, что приходит в голову, все игровое поле(ограничивающий все обьекты прямоугольник) разбить на регулярную сетку, в каждой ячейке будут храниться списки попадаемых в них ребер контуров. Таким образом, для проверки условного прожэктайла с ребрами выпускаем из каждой его точки лучи, направленные в сторону движения, и проверяем ребра в каждой попавшейся на их пути ячейке. Казалось бы на этом можно было бы остановиться. Но мы же ищем самый эффективный способ с учетом имеющихся ограничений. Поэтому пойдем дальше в наших рассуждениях и применим еще один дополнительный подход.
  Рассмотрим случай направленного движения на плоскости круглого снаряда P в сторону некого контура C, как показано на рисунке ниже CollisionExample0 | [Challenge] Просчет и оптимизация столкновений в 2D.
  В данном случае можно исключить из проверки ребра с номерами 1,4,5,6,7,8,9, которые не касаются заштрихованой зеленой области. Теперь, если распростанить подобный подход на произвольное направление, можно построить такой список ребер для каждого угла. Очевидно, что для некоторых диапазонов углов такие списки ребер будут одинаковыми, поэтому данный факт также можно использовать в дальнеших оптимизациях.
  Теперь осталось совместить оба подхода. Предполагается, что такая предстоящая реализация будет быстрее, чем использование какого-нибудь квадтри. Вобщем посмотрим, что с этого выйдет. Пока что хотелось бы услышать обсуждение собственно дальнейших оптимизаций обоих методов, а также возможно предложения о иных, более быстрых, методах.

#1
2:04, 6 дек 2022

жду бенчмарков в сравнении с box2d

#2
2:07, 6 дек 2022

  Ok, возможно. Но это скорее уже после Нового Года.

#3
2:29, 6 дек 2022

ArtProg
> Первое, что приходит в голову, все игровое поле(ограничивающий все обьекты
> прямоугольник) разбить на регулярную сетку, в каждой ячейке будут храниться
> списки попадаемых в них ребер контуров.
А чем тебе не подошел вариант: "нарезать невыкуплый полигон на выпуклые, и для выпуклых использовать GJK?"

#4
2:39, 6 дек 2022

Это такой уровень микро-оптимизаций, что нужно уже считать регистры и число мат-операций. Например, спатиал хеш грид будет тормозить до 100 сегментов. А наивная реализация тормозить после 100 сегментов. Или твоя плоскость медленнее чем перебрать ccw сегментов. Плюс SIMD и Ofast arch=native.

#5
2:51, 6 дек 2022

  MrShoor, ни разу не использовал данный алгоритм на практике, поэтому тут ничего не могу сказать. Но тогда вопрос. Может ли он отбрасывать неиспользуемые ребра эффективнее, чем хотя бы регулярная сетка с произвольным шагом(уровнем разбиения)?
  lookid, эти детали мне предстоит пока что выяснить.

#6
3:00, 6 дек 2022

ArtProg
> Может ли он отбрасывать неиспользуемые ребра эффективнее, чем хотя бы
> регулярная сетка с произвольным шагом(уровнем разбиения)?
Если ты собираешься строить эту сетку для ребер - то тебе каждый раз придется её перестраивать для динамических объектов, чтобы считать столкновения. А если в рассчет брать перестроение сетки, то GJK выигрывает ибо ему не нужна никакая сетка.
Вот тут я считаю суперофигенное объяснение GJK:

Запустить видео по клику - Как делать игрыЗапустить видео по клику - Как делать игры

Сам относительно недавно разобрался с этим алгоритмом (когда суслик меня пристыдил что я не знаю про GJK)

#7
3:25, 6 дек 2022

  MrShoor, мне пока что для статик контуров. Динамических обьектов, которые будут с ними сталкиваться, в рассматриваемом мною случае меньшинство. А для динамики(когда будет много прожэктайлов) наверное так и быть, воспользуюсь GJK. Спасибо также за видео! Довольно познавательно.

#8
6:57, 6 дек 2022

Сам делал так (только в 3D) когда понадобилось обрабатывать столкновения многогранников с большим числом граней. Время отсекания линейное от числа точек многоугольников.

Пусть A, B - 2 (не)выпуклых многоульника, v - вектор от центра А, к центру B.
Находим проекцию каждой точки объекта А на этот вектор, выбираем максимум.
Находим проекцию каждой точки объекта B на этот вектор, выбираем минимум.
Из А и B оставляем только те ребра, у которых проекция хотя бы одной из точек на v лежит между этим минимумом и максимумом.

#9
9:25, 6 дек 2022

ArtProg
> необязательно выпуклые
Или разбивать на выпуклые, или забыть про слово "оптимизация".

#10
10:01, 6 дек 2022

вектор минимального проникновения для двух невыпуклых многогранников вовсе не является комбинацией векторов проникновения попарно составляющих их выпуклых тел. общий случай обнаружения коллиженов для невыпуклых тел — это не то чтобы "посмотрим, успеем ли к новому году", это ближе к "мы всё ещё не знаем, как толком дать ему определение". причём это для статических. для динамических даже разговоров не идёт, лол.

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

#11
20:29, 8 дек 2022

  texture3D, хорошая идея. Но дело в том, что как раз факт столкновений вроде как достаточно легко проверяется с точки зрения алгоритмической(не вычислительной) сложности. И чтобы сократить число таких проверок, логично сократить число всех проверяемых ребер.
  То есть всякие регулярные сетки и прочие предрасчеты служат лишь для того чтобы упростить жизнь солверам. Ведь даже тот же алгоритм GJK будет строить симплексы не абы каким образом, а перебирая какие-то из ребер контуров. В идеале вижу этапы расчета столкновений такими:
1. Построить списки ребер таким образом, чтобы количество участвующих в расчете ребер было сведено к минимуму. Первый из рассмотренных в нулевом посте методов дает вроде желаемое на этом этапе. Второй метод нужно еще подкорректировать, так как там не все так гладко, как мне казалось сперва). Насчет применения квадтри, не уверен в его большей эффективности, чем уже упомянутые сетки, хотя бы в силу того, что дополнительные листья дерева все равно придется проверять.
2. Собственно определение расстояния вдоль вектора движения, на котором должен останавливаться условный снаряд при столкновении. Тут подойдет влобный расчет, если ребер мало. Или тот же GJK.
3. Построение векотора "отскока" или "скольжения". Тут могут быть применимы тоже сравнительно простые идеи, хотя и не без сюрпризов скорее всего).

ПрограммированиеФорумФизика

Тема в архиве.