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

Обработка столкновений 3d треугольник-треугольник

Страницы: 1 2 Следующая »
#0
1:04, 22 окт. 2019

Ок, предположим, что вектор перемещения vec3(0, 0, -1) и скорость (10), умножаем, треугольник смещается по Z на -10, столкновение треугольников засчитано, точки касания найдены. В идеале, следует провести расчет так, чтобы смещение было ограничено, скажем до 8, а точкой касания являлась вершина [a] (принадлежит треугольнику B). Я полагаю, что нужно вычислить ближайшую касательную (т.е вершину [a]). Каков алгоритм? Верно ли я копаю?
После чего, для большего числа треугольников, провести аналогичную операцию и вычислить ближайшую касательную среди них (и треугольник с данной касательной), в качестве "правильной" позиции столкновения использовать её с некоторым смещением против вектора направления?

Изображение

#1
1:35, 22 окт. 2019

Стоит погуглить separation axis theorem и minimum translation vector.

#2
(Правка: 4:08) 3:58, 22 окт. 2019

У тебя есть два положения до [a] и после [a]`. Где то между ними есть позиция где [a] лежит в плоскости B. Остается найти точку пересечения плоскости B и луча [a] [a]`. Вероятность того что у двух объектов есть больше одной точки касания, в том числе благодаря погрешностям вычисления, практически равна нулю. По этому максимальное расстояние от точки пересечения до второго положения покажет эту вершину из множества треугольников. Но точек касания в пределах 2 тактов может быть много и считать придется одну вершину на множество треугольников, а также этим же способом проверить противоположную модель, в целом M*N+L*K проверок.

Откуда взялись касательные непонятно, треугольник может выйти за другой полностью.

#3
5:14, 22 окт. 2019

DisconFord
> Каков алгоритм?
алгоритм таков, что никто не считает столкновение для произвольных triangle soup'ов. с ними всегда будут проблемы, которые принципиально невозможно решить за адекватное время. они всегда будут застревать друг в друге на более-менее сложной сцене, так как если взять, например, триангулированный стакан и затолкать в него триангулированный молоток в 2 раза больше него, то даже интуитивно трудно указать, что в этом случае считать точками и нормалями контакта. поэтому триангулированные модели практически всегда разбивают на выпуклые и далее пишут convex-convex collision, который гораздо лучше определён, чем triangle soup vs triangle soup.

#4
10:29, 22 окт. 2019

foxes
> треугольник может выйти за другой полностью
Кстати да.

foxes
> в целом M*N+L*K проверок
foxes
> покажет эту вершину
Вершина треугольника B(a) лежит в плоскости XY треугольника A, тут же можно определить расстояние, просто сделав трассировку по инвертированному вектору движения еще до момента перемещения, верно?

Suslik
> триангулированный стакан и затолкать в него триангулированный молоток в 2 раза
> больше него, то даже интуитивно трудно указать, что в этом случае считать
> точками и нормалями контакта.
А такое нельзя допускать. Наблюдал последствия даже в AAA-проектах, где юзают относительно свежие версии Havok и PhysX. Если что-то застряло (скорее всего по вине неправильного colisionmesh), то оно исправляется внешним воздействием и чисто случайно

#5
(Правка: 11:11) 10:53, 22 окт. 2019

DisconFord
> А такое нельзя допускать. Наблюдал последствия даже в AAA-проектах, где юзают
> относительно свежие версии Havok и PhysX. Если что-то застряло (скорее всего по
> вине неправильного colisionmesh), то оно исправляется внешним воздействием и
> чисто случайно
то есть ты думаешь, что у тебя денег больше, чем у них, чтобы подобные проблемы что ли решать? в AAA проектах такие косяки встречаются вовсе не потому что им лень было заморочиться на форуме тему создать, а потому что нормального решения просто не существует. более того, в большинстве AAA проектов тримеши даже не используются, тела застревают даже разбитые на конвексы.

DisconFord
> скорее всего по вине неправильного colisionmesh
проблема того, что ты называешь collisionmesh в том, что они не могут быть "неправильными". любая каша из треугольников — это, вообще говоря, корректный меш. то, что для него нельзя найти корректные коллижены — это проблема не меша, а самого подхода к поиску коллиженов для мешей. к слову, если ты думаешь, что найти коллижены для хотя бы двух треугольников просто, то попробуй погуглить, например, по запросу "triangle continuous collision detection" и удивись, что так не делает вообще никто. хинт: не потому что тебе первому такая идея в голову пришла.

там на самом деле был знойный пейпер когда-то давно про точное решение triangle vs triangle ccd, я его не могу найти. но вот нашёл пейпер с приблизительным решением: http://web.cse.ohio-state.edu/~wang.3602/Wang-2014-DCC/Wang-2014-DCC.pdf

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


foxes
> Вероятность того что у двух объектов есть больше одной точки касания, в том
> числе благодаря погрешностям вычисления, практически равна нулю
в случае контакта покоя между тел (в куче, например), между ними постоянно будет больше двух точек контакта неограниченно долго.

#6
11:34, 22 окт. 2019

Suslik
Ясно. Значит разделяющая ось.

#7
(Правка: 18:06) 18:00, 22 окт. 2019

Suslik
> будет больше двух точек
Объективно да, но конкретно между двумя объектами на 1 такт обычно 1 контакт. В состоянии покоя нет вектора движения и точки контакта таким образом отсутствуют. Это уже статическое пересечение объектов может дать множество точек.

DisconFord
> еще до момента перемещения, верно?
ну типа того.

#8
18:06, 22 окт. 2019

foxes
> В состоянии покоя нет вектора движения и точки контакта таким образом
> отсутствуют
куб под действитем гравитации стоит на плоскости

#9
(Правка: 23:10) 18:45, 22 окт. 2019

Suslik
Тогда это получается состояние вынужденного покоя, препятствия. Объект все равно движется, есть вектор. Такой случай как столкновение плоскостей.. тут прям бесконечное количество контактов.

#10
1:15, 23 окт. 2019

Suslik
> хороший реалтаймовый физический движок — это не тот, который этого не
> допускает

Да хоть какой. Хочу хоть что-то по этой части освоить, но я не надмозг, и если задача не будет решена в адекватные сроки - время сдаваться. 
Если нахождение коллизий SAT в 2D объяснено популярно, то для трехмерного случая - отнюдь. Вот и приходится сочинять, на пробу понимания.

#11
14:56, 23 окт. 2019

Почему бы и нет?
Изображение

Конечно, может быть случай, когда число точек, для которых справедливо Dot( d - c< moveVec) > 0 равно двум

#12
2:52, 24 окт. 2019

Насколько я понимаю после прочтения исходников Rigs of Rods, они проверяют только столкновение "вершина-треугольник". Это работает, если плотность вершин достаточная, хотя и может давать артефакты - иногда объекты могут пройти сквозь друг друга и потом зацепиться.

Такой упрощенный алгоритм позволяет им считать физику с большой частотой (2000 Гц) и обходиться без CCD.

В BeamNG физика вероятно работает так же.

#13
(Правка: 14:19) 13:44, 24 окт. 2019

Suslik
> если взять, например, триангулированный стакан и затолкать в
> него триангулированный молоток в 2 раза больше него, то даже
> интуитивно трудно указать, что в этом случае считать точками и
> нормалями контакта
Элементарно, надо двигать от прошлого положения, где пересечения еще не было, пока не упрется, Continous Collision Detection

> триангулированные модели практически всегда разбивают на
> выпуклые и далее пишут convex-convex collision
Ну запихни один выпуклый куб внутрь другого. И как тут искать точки и нормали контакта?

#14
13:47, 24 окт. 2019

DisconFord
Если пишешь CCD, надо рассматривать не треугольники против треугольников, а вершины против треугольников и ребра против ребер, т.к. вершина принадлежит нескольким треугольникам, а ребро - двум

Страницы: 1 2 Следующая »
ПрограммированиеФорумФизика