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

Столкновение движущихся вращающихся многоугольников (могут быть вогнутыми), а также кругов

#0
(Правка: 18:17) 18:15, 22 июля 2019

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

Нужно найти столкновения, если таковые произошли. А также посчитать в какую сторону и с какой силой нужно срикошетить.

Может кто-то подсказать эффективный и простой в реализации алгоритм?

Вычитание Минковского не подходит, т.к. многоугольники могут быть вогнутыми, а также могут вращаться (например, после столкновения). AABB тоже.

Прикол в том, что объекты не только вращаются, но еще и движутся и стреляют друг в друга объектами на больших скоростях.


#1
18:37, 22 июля 2019

Я так понимаю, можно адаптировать эту статью https://gamedev.ru/code/articles/?id=4249
но вогнутые объекты составлять из нескольких выпуклых многоугольников

#2
19:48, 22 июля 2019

Robotex
А чего ты просто Box2D не возьмешь?

#3
20:29, 22 июля 2019

Robotex
Ненадо разбивать на выпуклости, это глупости
Просто ищешь ближайшее пересечение пар вершина-сторона, с учетом их движения и вращения - это даст столкновение
Надо учесть, что при столкновении тела обмениваются как изменением импульса DP, так и изменением момента импульса
DM =  dot(DP,R), где R - вектор из центра масс в точку контакта
Момент импульс в 2D скаляр
Можно учесть и силы трения, считать |DP(тр)|<=K*|DP(реакт)|

#4
20:31, 22 июля 2019

а тут были? https://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B… 8%D0%BA%D1%83

#5
0:34, 23 июля 2019

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

#6
(Правка: 4:03) 4:01, 23 июля 2019

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

Salamandr
> а тут были? https://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B…
> 8%D0%BA%D1%83
от самого факта принадлежности точки многоугольнику для физики ни тепло ни холодно. нужно множество точек с нормалями, аппроксимирующим контактную площадку.

nigger
> Если все обозримо в пределах  допустимой памяти, то все грани проецируешь в
> некий массив акцепторов, просто чисел, а все взаимодействия это
> сложения/вычитания
дай угадаю, сам ты это никогда не программировал.

#7
19:41, 23 июля 2019

baraff
mirtich
jiglib-0.84
box2d
bullet physics
chipmunk physics
RandyGaul ImpulseEngine

Если не хочешь изучать всё, то используй segment mesh + normals. Это как triangle mesh, только 2D.

#8
20:26, 23 июля 2019

Suslik
Делал 2д 1000 псевдосфер. Не тормозит. Но всю сцену сводишь к массиву интов, это не совсем физика. Там конечный автомат.

#9
13:41, 26 июля 2019

Сделал quadtree для физики:

QuadTree Spatial Partitioning | Столкновение движущихся вращающихся многоугольников (могут быть вогнутыми), а также кругов


А как его теперь по грамотному обойти?

У меня два варианта:

1. Каждый объект попадает только в тот квадрат, в котором лежит его центр. Соответственно нужно проверить этот квадрат на столкновения и все прилегающие. И вот как эти прилегающие определить и обработать?

2. Каждый объект, может попасть в несколько квадратов, с которыми он пересекается. Тогда на столкновения нужно проверить только этот конкретный квадрат (просто пройти по всем квадратам и попересекать объекты. Но это не будет работать в случае, как на картинке, когда в квадрате только один объект). Верно?
Но если для столкновений это сгодится, то уже не сгодится для дальнобойной атаки (т.к. один объект из одного квадрата, может атаковать объект из другого квадрата).


Как лучше всего поступить?

#10
15:17, 26 июля 2019

Robotex
> А как его теперь по грамотному обойти?
чувствую, в твоей реализации octree будет медленнее, чем без него. для шаров одинакового размера регулярная сетка с шагом, равным диаметру шаров, будет гораздо эффективнее.

#11
16:10, 26 июля 2019

Suslik
> для шаров одинакового размера
В игре будут использоваться в итоге многоугольники разного размера

#12
15:00, 28 июля 2019

Robotex
В квадтри многоугольник может перекрывать несколько узлов, притом даже вершины могут не содержатся в перекрытом узле, надо считать пересечение многоугольника с прямоугольником через SAT

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