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

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

Страницы: 1 2
#15
14:12, 24 окт. 2019

Aslan
> Элементарно, надо двигать от прошлого положения, где пересечения еще не было,
> пока не упрется. Это называется Continous Collision Detection
ну допустим, они пересеклись в момент времени 0 (кстати, чтобы точно найти этот момент для двух треугольников, нужно, кажется, решить уравнение 4 степени, что в принципе не решается в квадратурах), так как молоток уже лежит на стакане. твои дальнейшие действия?

> Ну запихни один выпуклый куб внутрь другого. И как тут искать точки и нормали контакта?
minimal translation distance можно для конвексов посчитать точно и, расталкивая тела в этом направлении, они гарантированно не провалятся друг в друга дальше. точность обнаружения конкретных точек и нормалей здесь особой роли не играет.


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

Suslik
> ну допустим, они пересеклись в момент времени 0 (кстати,
> чтобы точно найти этот момент для двух треугольников, нужно,
> кажется, решить уравнение 4 степени
Ур-е 1й степени, прямолинейно движущиеся вершины против треугольника и ребра против ребер

> уравнение 4 степени, что в принципе не решается в квадратурах
Формула Феррари в помощь )

> молоток уже лежит на стакане. твои дальнейшие действия?
Выше написал. Два варианта:
1) откатить молоток взад по прямой откуда он приехал до точки первого контакта и там оставить
2) откатить время, вернее всегда считать время до первого collision - что может быть накладно

> minimal translation distance можно для конвексов посчитать
точно и, расталкивая тела в этом направлении, они гарантированно не провалятся друг в друга дальше. точность обнаружения конкретных точек и нормалей здесь особой роли не играет.
Через SAT? Может быть, но разбивая на convex ты плодишь вершины и грани. Твой же пример - граненный стакан

Ну ok, разбили молоток на convex-ы, для каждого отдельно применили выталкивание - и молоток разорвался?

#17
14:56, 24 окт. 2019

Aslan
> Ур-е 1й степени, прямолинейно движущиеся вершины против треугольника и ребра
> против ребер

погоди, сусел конечно хрню порит местами, но разве тело двигаясь прямолинейно не вращается при этом? Т.о. у тебя вершины по спирали двигаются, а это уже кривые 2го порядка. Что уже посложнее, но в принципе решаемо, наверно.


Suslik
Слово "квадратура", соотносится с дифф уравнениями и интегрированием. Здесь же речь об алгебраическом.

https://en.wikipedia.org/wiki/Quadrature

Ну когда ты уже терминами перестанешь сыпать ))

#18
15:02, 24 окт. 2019

slepov
> разве тело двигаясь прямолинейно не вращается при этом?
> у тебя вершины по спирали двигаются, а это уже кривые 2го порядка
Про вращение вроде не говорили. Сведется к квадратному уравнению

#19
(Правка: 16:30) 16:17, 24 окт. 2019

Aslan
> 1) откатить молоток взад по прямой откуда он приехал до точки первого контакта
> и там оставить
> 2) откатить время, вернее всегда считать время до первого collision - что может
> быть накладно
случай контакта покоя, когда одно тело стоит на другом. куда откатывать, если оно там уже час стоит?

> Через SAT? Может быть, но разбивая на convex ты плодишь вершины и грани. Твой же пример - граненный стакан
в случае с гранёным стаканом вообще всё плохо. его как ни представляй, всегда можно будет сломать. однако, если представлять его независимыми треугольниками, то шансов сломать будет гораздо больше, потому что тогда можно ещё застрять, например, просто в грани. если грани представить как выпуклые тела, то хотя бы в них не застрянет.

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

slepov
> Слово "квадратура", соотносится с дифф уравнениями и интегрированием.
имелось в виду, что уравнения выше четвёртой степени аналитически не решаются в общем виде

#20
(Правка: 18:47) 18:04, 24 окт. 2019

Suslik
> случай контакта покоя, когда одно тело стоит на другом. куда
> откатывать, если оно там уже час стоит?
А зачем откатывать, если нет пересечения?
Или ты имеешь в виду что сила тяжести утянет вниз и пересечение появится через бесконечно малое время?
Действуем по варианту 1 - берем фиксированный dt, опускаем стакан (силой тяжести) ниже стола, а потом откатываем обратно вверх, разница с твоим подходом, что вектор выталкивания считаю через CCD.
Другими словами, можно откатывать во времени отдельное тело или всю систему

> в случае с гранёным стаканом вообще всё плохо. его как ни представляй, всегда можно будет сломать. однако, если представлять его независимыми треугольниками, то шансов сломать будет гораздо больше, потому что тогда можно ещё застрять, например, просто в грани. если грани представить как выпуклые тела, то хотя бы в них не застрянет.
Что называешь "сломать"?
Как можно застрять в грани?
И я не предлагал представлять независимыми треугольниками, я считаю CCD для мешей, вершина-грань, ребро-ребро

> не может оно свестись к квадратному уравнению, так как в общем случае даже двух вращающихся прямых, моментов контакта будет бесконечно много (из-за цикличности вращения)
Лень считать, рассмотрим простейший случай - пересечение прямой и окружности.
Если брать угол - то цикличность +2*PI*N, если брать (X,Y) - то лишь 2 точки

CCD всеравно считается на малых промежутках, т.к. тела испытывают силы, ускоряются итд, вращение можно грубо считать дискретным поворотом через dt

Ось выталкивания двух convex-ов берешь из SAT (нормаль или векторное произведение ребер с мин длиной пересечения проекций) ?
N^2 осей, для каждой считать проекцию тел - уже N^3
Как ты считаешь общую ось выталкивания для объединения convex-ов?

#21
22:38, 24 окт. 2019

Suslik
Хотел задать вопрос, если convex меши правят балом, то каким образом в геймдеве делают "корзины"? Там же литой бокс получается.

#22
(Правка: 0:16) 0:13, 25 окт. 2019

DisconFord
> то каким образом в геймдеве делают "корзины"?
Вот таким:


Еще в 7:00 красивый пример "корзины".
#23
0:47, 25 окт. 2019

MrShoor
> Еще в 7:00 красивый пример

3:03 - автомат для выдачи ведер не выкинул же такой трюк. Хотя остальные корзины - чистой воды динамика, в доках к bullet предлагается пихать всю динамику в convex, для статики вроде это не критично.

#24
0:53, 25 окт. 2019

DisconFord
> 3:03 - автомат для выдачи ведер не выкинул же такой трюк.
Он и не должен был его выкинуть. Во первых там нет контакта со стенками, а во вторых выдача ведра наверняка заскриптована.

#25
(Правка: 2:52) 2:51, 25 окт. 2019

MrShoor
> Еще в 7:00 красивый пример "корзины".
кто-то может сказать, мол : "пф, какой-то ноунейм viscera cleanup detail". так, для справки, это — source engine, который работает на havok. у них одни из самых продвинутых коллиженов (по крайней мере лучше наколеночных буллетов). и нет, вёдра застревают друг в друге вовсе не потому что этого никто не заметил или кому-то было лень создать тему вроде этой на форуме.

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

#26
9:10, 25 окт. 2019

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

Пугает, что даже железобетонная казалось бы классика из 90-х с этим не справлялась:

Наглядный пример что происходит на 5:30 и чуть дальше.

#27
13:35, 25 окт. 2019

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

А можно просто захардкодить конкретно для ведер специальную логику, и всего делов. Раз уж у тебя игра такая, про помещение ведер друг в друга. Сразу видится несколько хаков разной сложности - самый продвинутый, наверное, это отключать для стекнутых объектов взаимные коллизии и заменять связь разрушаемым шарниром с ограничением по углу.

#28
(Правка: 6:10) 6:08, 20 янв. 2020

polvorony
> Насколько я понимаю после прочтения исходников Rigs of Rods, они проверяют
> только столкновение "вершина-треугольник". Это работает, если плотность вершин
> достаточная, хотя и может давать артефакты - иногда объекты могут пройти сквозь
> друг друга и потом зацепиться.
>
> Такой упрощенный алгоритм позволяет им считать физику с большой частотой (2000
> Гц) и обходиться без CCD.
>
> В BeamNG физика вероятно работает так же.
Посмотрел на ютубе - хорошо работает. Надо взять на вооружение.
А то делал проверку "ландшафт - сфера" - кое-как сделал, но намучался пипец, а начал делать "ландшафт - AABB" - там вообще кромешный ад, если делать точно и правильно - слишком уж много проверок получается.

#29
18:44, 17 фев. 2020

DisconFord постановка задачи вроде простая, а решение сложное. Я не знаю правильного и оптимального решения. Предложу своё, а там пригодится оно или нет, дело второе.
1 Определяем стоит ли вообще связываться с расчётом столкновения или нет. Должна быть сфера относительно условного центра фигуры. Если объект приблизился ближе радиуса - считаем, дальше - не считаем
2 смотрим параллельны ли плоскости треугольников.
2.1 Если да, ищем расстояние между плоскостями треугольников.
2.2 Если оно ровно 0, то ищем принадлежность a,b,c внутреннему пространству другого треугольника. Находим значит касаются.
2.3 Ищем пересечения линий a1,b1 c a2,b2 a2,c2, b2,c2 и тд. Если есть - значит касаются.
3 Ищем расстояние от а,b,c до плоскости другого треугольника
3.1 Если оно меньше чем до соседней точки - ищем пересечение с внутренним пространством другого треугольника.
3.2 Если эта точка внутри треугольника, то есть пересечение.

Страницы: 1 2
ПрограммированиеФорумФизика