Я еще заранее собираю тела в правильной кристаллической решетке (6-гранные соты). Все связи заданы заранее в 6 направлениях от каждой частицы.
Не делал точных замеров но по ощущениям увеличивает эффективную прочность тел.
Поток на частицу? У Вас тысячи потоков? А структура данных по которой вы ищете ближайших соседей синхронизуется каждый тик по всему объему? Мне не доводилось считать на GPU не знаю особенностей.
Я предполагал что-то вроде разбиения сцены на N не пересекающихся участков и в каждом обсчитывать все частицы в одном потоке. Возникают нюансы синхронизации на стыке этих участков.
Эффективность я оцениваю так: на одной и той же сцене какой максимальной длинны можно сделать шаг интегрирования прежде чем все взрывается. От метода зависит очень слабо.
Рунге-Кутта не пробовал, вычислительно сложнее а выигрыш точности явно не скомпенсирует этого. Тут бы придумать что-то для неравномерного интегрирования, чтобы одни частицы чаще другие реже…
Спасибо за информацию и ссылки, обязательно почитаю.
Как я понимаю, там все же больше уклон именно в точное моделирование для научных целей. Тут нужно для игры и приемлемы любые хаки, которые сохранят визуальную правдоподобность и не более.
Кстати, а какой метод интегрирования у Вас?
У меня Верле, хотя и Эйлер не сильно по эффективности отличается (по экспериментам: процентов на 10 примерно уменьшение шага интегрирования компенсирует разницу между ними)
Да это в реальном времени около 2000 частиц, в один поток, на CPU, на Mac Pro 2015.
Чтобы получить такую жесткость действительно пришлось сильно уменьшить шаг интегрирования (100 микросекунд), при большем шаге тела ближе к пудингу. Вообще асимптотика нагрузки на CPU от «жесткости» не знаю какая но очень крутая, надо как-нибудь попробовать вывести… Давно мечтаю придумать что-нибудь чтобы ее улучшить, но идеи пока сырые… ))
Но в такой конфигурации сил тела по крайней мере сохраняют форму. Я тоже пробовал с силой Леннарда-Джонса, но тела тогда расползаются и деформируются, а тут гнутся до предела — потом рвутся. Наверно так можно разные материалы моделировать.
Поделюсь своим опытом:
Я как-то тоже делал такой 2D физический движек, сила взаимодействия между частицами у меня была 2 типов:
1) отталкивающая между любыми близкими частицами
2) заранее (при конструировании мира) заданный набор притягивающих связей. Эти связи разрушались, если частицы отдалялись друг от друга далее определьного расстояния.
Вместо желе получились вполне нормальные упругие тела.
Количество частиц не единственный параметр, важна частота итераций. Чем больше интервал интегрирования тем менее твердые и более желеобразные тела у вас получатся.
На современном i5 (CPU), в реалтайме (2D) мне удалось максимум выжать 20 000 частиц на 2 000 итераций интегрирования в секунду в один поток (это был эксперимен из любопытства, распараллелить не дошли руки).
Это тела с жесткостью визуально как у ластика.
Не думаю что возможно сильно больше, это примерно 7 связей на частицу, того около 300 000 000 связей в секунду.
Мне в голову сразу приходит реализация определения области видимости с использованием метод заметающей прямой:
1) Отсортировать все вершины граней препятствий по часовой стрелке
2) Двигать заметающую прямую по кругу вокруг NPC — отслеживать ближайшую грань препятствий
3) на каждом участке до следующей вершины определять зону видимости в этой части сектора (по расположению ближайшей грани относительно сектора видимости: либо полный кусочек сектора, либо обрезанный гранью)
В результате должна получиться область видимости.
Оценка эффективности — O(N*log(N)), где N — количество вершин препятствий около NPC (можно предварительную выборку сделать ограничивающим прямоугольником).
Мне пока не доводилось решать задачу определения области видимости, могу что-то упускать.
Вы не рассматривали такой алгоритм, и если да — то чем не подходит?
Оценка не совсем верная, это не совсем O(sqr(N)). Такое время доступа только к самой медленной части памяти. И хотя ее больше всего, но алгоритм может использовать «в основном» небольшой объем памяти.
Например, если частота обращения к «отдаленным» областям памяти убывает экспоненциально с ростом «удаленности» данных, тогда для алгоритма асимптотическая оценка времени доступа к памяти совсем другая будет.
Эволюция технологий в действии, через несколько лет 99% упомянутых тут технологий забудут как страшный сон и появится еще больше новых… А может случится массовое вымирание, и снова все будет просто и понятно. Даже жалко время тратить на освоение современных зоопарков.
В статье есть примеры что можно легко обмануть сетку если знать чему она внутри себя таки наобучалась.
А если так придумать специальную картинку, показал ее автопилоту машины едущему по дороге — и он в ужасе свернул в обрыв…
Хотя, наверно, такое и с человеком сработает :))
В общем «нейронки» классная штука, но точная математика с аналогичным результатом лучше.
Нейронные сети непредсказуемы. Они обучаются на конкретной выборке, а что выдадут для незнакомой картинки неизвестно. Тому даже примеры в статье автор привел.
Совсем не факт что надо искать именно биологически правдоподобный метод, эволюция не всегда может использовать оптимальный подход. Полностью смоделировать человеческий мозг пока невозможно, но может это и не надо? может есть способ проще?
Строгая математика тем хороша, что ее легко воспроизвести, можно предсказать результат на любых входных данных. Вы бы доверили свою жизнь нейронной сети управляющей автомобилем, которая неизвестно как отреагирует на незнакомую ситуацию?
Не делал точных замеров но по ощущениям увеличивает эффективную прочность тел.
Я предполагал что-то вроде разбиения сцены на N не пересекающихся участков и в каждом обсчитывать все частицы в одном потоке. Возникают нюансы синхронизации на стыке этих участков.
Рунге-Кутта не пробовал, вычислительно сложнее а выигрыш точности явно не скомпенсирует этого. Тут бы придумать что-то для неравномерного интегрирования, чтобы одни частицы чаще другие реже…
Как я понимаю, там все же больше уклон именно в точное моделирование для научных целей. Тут нужно для игры и приемлемы любые хаки, которые сохранят визуальную правдоподобность и не более.
У меня Верле, хотя и Эйлер не сильно по эффективности отличается (по экспериментам: процентов на 10 примерно уменьшение шага интегрирования компенсирует разницу между ними)
Чтобы получить такую жесткость действительно пришлось сильно уменьшить шаг интегрирования (100 микросекунд), при большем шаге тела ближе к пудингу. Вообще асимптотика нагрузки на CPU от «жесткости» не знаю какая но очень крутая, надо как-нибудь попробовать вывести… Давно мечтаю придумать что-нибудь чтобы ее улучшить, но идеи пока сырые… ))
Но в такой конфигурации сил тела по крайней мере сохраняют форму. Я тоже пробовал с силой Леннарда-Джонса, но тела тогда расползаются и деформируются, а тут гнутся до предела — потом рвутся. Наверно так можно разные материалы моделировать.
Я как-то тоже делал такой 2D физический движек, сила взаимодействия между частицами у меня была 2 типов:
1) отталкивающая между любыми близкими частицами
2) заранее (при конструировании мира) заданный набор притягивающих связей. Эти связи разрушались, если частицы отдалялись друг от друга далее определьного расстояния.
Вместо желе получились вполне нормальные упругие тела.
На современном i5 (CPU), в реалтайме (2D) мне удалось максимум выжать 20 000 частиц на 2 000 итераций интегрирования в секунду в один поток (это был эксперимен из любопытства, распараллелить не дошли руки).
Это тела с жесткостью визуально как у ластика.
Не думаю что возможно сильно больше, это примерно 7 связей на частицу, того около 300 000 000 связей в секунду.
1) Отсортировать все вершины граней препятствий по часовой стрелке
2) Двигать заметающую прямую по кругу вокруг NPC — отслеживать ближайшую грань препятствий
3) на каждом участке до следующей вершины определять зону видимости в этой части сектора (по расположению ближайшей грани относительно сектора видимости: либо полный кусочек сектора, либо обрезанный гранью)
В результате должна получиться область видимости.
Оценка эффективности — O(N*log(N)), где N — количество вершин препятствий около NPC (можно предварительную выборку сделать ограничивающим прямоугольником).
Мне пока не доводилось решать задачу определения области видимости, могу что-то упускать.
Вы не рассматривали такой алгоритм, и если да — то чем не подходит?
Например, если частота обращения к «отдаленным» областям памяти убывает экспоненциально с ростом «удаленности» данных, тогда для алгоритма асимптотическая оценка времени доступа к памяти совсем другая будет.
А если так придумать специальную картинку, показал ее автопилоту машины едущему по дороге — и он в ужасе свернул в обрыв…
Хотя, наверно, такое и с человеком сработает :))
В общем «нейронки» классная штука, но точная математика с аналогичным результатом лучше.
Совсем не факт что надо искать именно биологически правдоподобный метод, эволюция не всегда может использовать оптимальный подход. Полностью смоделировать человеческий мозг пока невозможно, но может это и не надо? может есть способ проще?
Строгая математика тем хороша, что ее легко воспроизвести, можно предсказать результат на любых входных данных. Вы бы доверили свою жизнь нейронной сети управляющей автомобилем, которая неизвестно как отреагирует на незнакомую ситуацию?
В общем, подробный комментарий к методу — и решение будет идеально.