Алгоритм распространения пламени

← →
Ламо777 © (2013-12-23 16:39) [0]

Доброго времени суток!

Встала задача - реализовать мат.модель распрострения возгорания на плоскости. Отображаться распрострение возгорания будет в графическом движке (Unity3D). Модель распространения я собирался реализовать также в скриптах Unity, но на первых же шагах столкнулся с проблемами производительности. Просто "подготовка" простейшей плоскости занимает до 2 минут. А ведь данный расчеты нужно в каждом кадре (фрейме), около 30 раз в секунду.
Кто сталкивался с подобными задачами, на моделирование каких-либо быстротекущих процессов? Какие инструменты, подходы, алгоритмы использовали?

← →
Rouse_ © (2013-12-23 16:46) [1]

Спроси у Юры Зотова, он этим немного занимался, докторскую чтоль писал :))

← →
Ламо777 © (2013-12-23 16:52) [2]

> Спроси у Юры Зотова, он этим немного занимался, докторскую
> чтоль писал :))

Надеюсь, он сюда заглянет)

← →
icelex © (2013-12-23 17:26) [3]

> Кто сталкивался с подобными задачами, на моделирование каких-
> либо быстротекущих процессов?

следует отделить расчет от отображения

← →
Ламо777 © (2013-12-23 17:44) [4]

> следует отделить расчет от отображения

Я тоже пришел к такому решению).
Думаю, расчет делать на отдельном сервисе, но есть несколько вопросов.
Площадь, по которой будет распространяться пламя, я моделирую в виде плоскости, состоящей из множества полигонов(четырехугольников). Один из полигонов назначается "точкой возгорания", и дальше уже пламя распространяется согласно определенным формулам. Т.е. по определенным правилам полигоны, соседствуюище с точкой возгорания, обозначаются как (не)горящие, и так далее.
Для работы с полигонами (и вообще с геометрией) в Unity3D есть достаточное удобный API. Если же я вынесу расчет модели куда-то наружу, то придется все геометрические расчеты (нахождение соседних полигонов, нахождение полигонов вписанных в окружность и тому подобное) реализовывать самому. Я планировал сделать сервис для расчета на C#, но сомневаюсь, что в нем удобно работать с геометрией.

← →
Jeer © (2013-12-23 17:57) [5]

Может, "дял анчала", стоит с горшка слезть? :)

← →
icelex © (2013-12-23 18:01) [6]

> но сомневаюсь, что в нем удобно работать с геометрией.

Для меня это, если честно, загадочное утверждение, не понимаю, что оно может значить. Писать лень? Ну так стоит поискать тогда библиотеки свободные, хоть на том же codeproject.com.

← →
Ламо777 © (2013-12-23 18:02) [7]

> Может, "дял анчала", стоит с горшка слезть?

А что для этого нужно сделать? Поделитесь ссылками.

← →
Юрий Зотов © (2013-12-23 18:04) [8]

Расчетами - занимался. Визуализацией расчетов - не занимался.

← →
картман © (2013-12-23 18:07) [9]

формулы... а как описать флуктуации?

← →
Pavia © (2013-12-23 18:11) [10]

У меньше коэффициент масштаба и будет работать быстрее.

← →
Юрий Зотов © (2013-12-23 18:15) [11]

> картман © (23.12.13 18:07) [9]
> формулы... а как описать флуктуации?

В этой задаче таких "как" - выше крыши.

← →
Ламо777 © (2013-12-23 18:19) [12]

> формулы... а как описать флуктуации?

Флуктуации описывать не нужно. Считаем, что возгорание распространяется равномерно.

← →
Dimka Maslov © (2013-12-23 18:31) [13]

Надо начинать с модели мат. модели сферического возгорания в вакууме.

← →
Inovet © (2013-12-23 18:46) [14]

> [13] Dimka Maslov © (23.12.13 18:31)
> Надо начинать с модели мат. модели сферического возгорания в вакууме

Да. Моделирование звезды.

← →
Pavia © (2013-12-23 18:52) [15]

А разве в вакууме может быть возгорание?

← →
antonn © (2013-12-23 19:03) [16]

> Ламо777 © (23.12.13 16:39)

а что тормозит - расчет или графика?

← →
Dimka Maslov © (2013-12-23 19:08) [17]

> Pavia © (23.12.13 18:52) [15]

Согласен. Получается тривиальное решение, равное нулю. Ну у нас же математическая абстракция. Введём в задачу условие, что сферический очаг возграния в вакууме содержит достаточное количество окислителя и топлива.

← →
Sapersky (2013-12-23 19:11) [18]

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

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

Можно использовать битмап (легко рисовать для отладки) или двумерный массив. Операция - в простейшем случае блюр (размазывание по маске 3*3) или dilation:
http://homepages.inf.ed.ac.uk/rbf/HIPR2/dilate.htm
Ну и понятно что возможны (точнее нужны, чтобы было похоже на правду) разные навороты. Например, отдельная карта (опять же битмап/массив), в которой хранится горючесть для всех ячеек, и ест-но огонь скорее будет двигаться в сторону более горючих. Плюс ещё ветер. Можно учитывать перепад высот на местности (ещё карта), хотя навскидку сложно сказать, как это будет влиять.

← →
Юрий Зотов © (2013-12-23 19:41) [19]

> Ламо777 © (23.12.13 18:19) [12]

Самый примитивнейший способ: для горизонтальной плоскости допускаем, что скорость распространения пламени V одинакова во все стороны, постоянна во времени и известна из эксперимента. Тогда площадь горения имеет форму круга радиусом Vt (где t - время). Но это очень грубый подход и хорош он лишь тем, что с визуализацией прямо в процессе расчета не будет никаких проблем.

Другой подход - разбить площадь на квадраты (как Вы и хотели) и считать, что над каждым квадратом есть свой султанчик пламени. Тогда задача сводится к решению неслабой системы диффуров в частных производных, а о визуализации прямо в процессе расчета можно даже и не мечтать. Хорошо, если 1 минуту реального времени удастся просчитать за несколько часов машинного времени.

← →
Ламо777 © (2013-12-23 20:41) [20]

> Самый примитивнейший способ: для горизонтальной плоскости
> допускаем, что скорость распространения пламени V одинакова
> во все стороны, постоянна во времени и известна из эксперимента.
> Тогда площадь горения имеет форму круга радиусом Vt (где
> t - время)

Именно такую модель я и реализовываю. Разбитие на квадраты необходимо потому, что в трехмерной графике любая плоскость состоит из полигонов, и площадь возгорания в любом случае придется "вписывать" в некое количество полигонов.

← →
Ламо777 © (2013-12-23 20:46) [21]

> а что тормозит - расчет или графика?

Тормозят элементарные операции - закрашивание полигонов на плоскости. Для 10 000 полигонов эта операция занимает порядка 2-3 минут.

> Если это регулярная сетка (квадраты), то не стоит использовать
> полигоны.

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

> Ну и понятно что возможны (точнее нужны, чтобы было похоже
> на правду) разные навороты. Например, отдельная карта (опять
> же битмап/массив), в которой хранится горючесть для всех
> ячеек, и ест-но огонь скорее будет двигаться в сторону более
> горючих.

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

← →
Ламо777 © (2013-12-23 20:50) [22]

> Можно использовать битмап (легко рисовать для отладки) или
> двумерный массив. Операция - в простейшем случае блюр (размазывание
> по маске 3*3) или dilation

Пробежал по диагонали, ничего не понял. Попробую разобраться, спасибо.

← →
antonn © (2013-12-23 20:50) [23]

> Тормозят элементарные операции - закрашивание полигонов
> на плоскости. Для 10 000 полигонов эта операция занимает
> порядка 2-3 минут.

элементарная она только на словах, зря что ли существуют задротские методы оптимизации и через-гландовые способы вывода графики? :)

← →
Ламо777 © (2013-12-23 21:07) [24]

> элементарная она только на словах, зря что ли существуют
> задротские методы оптимизации и через-гландовые способы
> вывода графики? :)

Уже наше на хабре статейку про параллельную обработку данных на R :-)

← →
Sapersky (2013-12-23 21:12) [25]

В Фаркрае вон регулярная сетка, для ландшафта 2D, для объектов 3D:
http://jflevesque.com/2012/12/06/far-cry-how-the-fire-burns-and-spreads/
(нагуглено за 10 секунд по фразе "fire propagation")

Почему я упоминал блюр/размазывание: мне показалось, что распространение огня на регулярной сетке можно сделать похоже, обходим все ячейки и для каждой считаем её состояние в зависимости от соседних.
Хотя можно наоборот, обходить только ячейки с огнём и если у них есть соседние негорящие, поджигать их. Для небольшой площади возгорания наверное эффективнее.

> > Тормозят элементарные операции - закрашивание полигонов
> > на плоскости. Для 10 000 полигонов эта операция занимает
> > порядка 2-3 минут.

Точно руки кривые. Закраска 10 000 полигонов занимает 100 000 тактов. Даже если вы умудритесь накасячить, то 1 000 000 тактов что менее 1 мс. И это если не вспоминать про оптимизацию.

> Тогда задача сводится к решению неслабой системы диффуров
> в частных производных, а о визуализации прямо в процессе
> расчета можно даже и не мечтать. Хорошо, если 1 минуту реального
> времени удастся просчитать за несколько часов машинного
> времени.

Почему в частных? Ну если решать точно, то да. А если приближённо, с погрешностью, то будет в реальном времени всё крутиться. К примеру через оператор Blur.

> Точно руки кривые. Закраска 10 000 полигонов занимает 100
> 000 тактов. Даже если вы умудритесь накасячить, то 1 000
> 000 тактов что менее 1 мс. И это если не вспоминать про
> оптимизацию.

Вообще-то, это только так говорится - "закраска 100 000 полигонов"))). Каждый полигон состоит из 2-х треугольников. Для каждого треугольника нужно проделать несколько операций - найти его вершины, пересчитать нормали, найти смежный треугольник для построения четырехугольника и т.д.

>
> > Точно руки кривые. Закраска 10 000 полигонов занимает
> 100 > 000 тактов. Даже если вы умудритесь накасячить, то
> 1 000 > 000 тактов что менее 1 мс. И это если не вспоминать
> про > оптимизацию.Вообще-то, это только так говорится -
> "закраска 100 000 полигонов"))). Каждый полигон состоит
> из 2-х треугольников. Для каждого треугольника нужно проделать
> несколько операций - найти его вершины, пересчитать нормали,
> найти смежный треугольник для построения четырехугольника
> и т.д.

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

А освоить CUDA(PhysX) не вариант? Пущай видяхо все считает, зря что ли ядер понапихали туда кучу? и визуализацией пущай занимается. Проц только руками водить должен в современном мире и данные подгружать.

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

Нужно именно что моделировать все, без разделения на видимое/невидимое. Т.е. распространение возгорания должно происходить реалистично.

> А освоить CUDA(PhysX) не вариант? Пущай видяхо все считает

Даже не знаю, с какого боку подходить. Можешь кинуть ссылкой?

← →
robt5 (2013-12-23 21:58) [33]

есть готовый движок ДУНЯ используется в игре фаркрай 2

>
> Ламо777 © (23.12.13 16:39)
>
> Доброго времени суток!
>
> Встала задача - реализовать мат.модель распрострения возгорания

если не секрет, в связи с чем и для чего такая задача появилась?

> > Тогда надо оптимизировать. Обрабатывать только те полигоны
> > которые попадают в текущий кадр, а также сделать не равномерную
> > сетку.Нужно именно что моделировать все, без разделения
> на видимое/невидимое. Т.е. распространение возгорания должно
> происходить реалистично.

Закраска к моделированию не относится.

Алгоритм распространения пламени Найти похожие ветки