Метод установки уровня

Видео спирали, распространяющейся по наборам уровней ( кривизна потока ) в 2D. Левое изображение показывает решение нулевого уровня. На правом изображении показано скалярное поле с заданным уровнем.

Метод набора уровней ( LSM это концептуальная основа использования наборов уровней в качестве инструмента численного анализа поверхностей ) — и форм . LSM может выполнять численные вычисления с использованием кривых и поверхностей на фиксированной декартовой сетке без необходимости параметризации этих объектов. ^[1] LSM упрощает выполнение вычислений над формами с острыми углами и формами , которые меняют топологию (например, путем разделения на две части или образования отверстий). Эти характеристики делают LSM эффективным для моделирования объектов, изменяющихся во времени, таких как надувающаяся подушка безопасности или капля масла, плавающая в воде.

Обзор

Рисунок справа иллюстрирует несколько идей по поводу LSM. В верхнем левом углу находится ограниченная область с корректной границей. Ниже красная поверхность представляет собой график функции заданного уровня. $\varphi$ определяя эту форму, а плоская синяя область представляет плоскость XY . Тогда граница формы представляет собой набор нулевого уровня $\varphi$ , а сама форма представляет собой набор точек на плоскости, для которых $\varphi$ положительное значение (внутри фигуры) или ноль (на границе).

В верхнем ряду топология фигуры меняется, поскольку она разделена на две части. Это преобразование сложно описать численно, параметризовав границу формы и проследив ее эволюцию. Алгоритм можно использовать для определения момента разделения формы на две части, а затем построить параметризацию для двух вновь полученных кривых. Однако в нижнем ряду плоскость, в которой производится выборка функции набора уровней, перемещается вверх, на которой описывается изменение топологии формы. Гораздо проще работать с формой через ее функцию установки уровня, чем непосредственно с самой собой, при этом методу необходимо учитывать все возможные деформации, которым может подвергнуться форма.

Таким образом, в двух измерениях метод набора уровней представляет собой замкнутую кривую. $\Gamma$ (например, граница формы в нашем примере) с помощью вспомогательной функции $\varphi$ , называемая функцией установки уровня. Кривая $\Gamma$ представляется как набор нулевого уровня $\varphi$ к

\Gamma =\{(x,y)\mid \varphi (x,y)=0\},

и метод levelset манипулирует $\Gamma$ неявно через функцию $\varphi$ . Эта функция $\varphi$ предполагается, что он принимает положительные значения внутри области, ограниченной кривой $\Gamma$ и отрицательные ценности снаружи. ^[2]^[3]

Уравнение установки уровня

Если кривая $\Gamma$ движется в нормальном направлении со скоростью $v$ , то с помощью цепного правила и неявного дифференцирования можно определить, что функция уровня $\varphi$ удовлетворяет уравнению набора уровней

{\frac {\partial \varphi }{\partial t}}=v|\nabla \varphi |.

Здесь, $|\cdot |$ - евклидова норма (обычно обозначаемая одиночными чертами в уравнениях в частных производных), и $t$ это время. Это уравнение в частных производных , в частности уравнение Гамильтона–Якоби , и его можно решить численно, например, с помощью конечных разностей на декартовой сетке. ^[2]^[3]

Однако численное решение уравнения набора уровней может потребовать применения передовых методов. Простые методы конечных разностей быстро терпят неудачу. Методы восходящей намотки , такие как метод Годунова, считаются лучшими; однако метод установки уровня не гарантирует сохранения объема и формы заданного уровня в поле адвекции, сохраняющем форму и размер, например, однородном или вращательном поле скоростей. Вместо этого форма набора уровней может исказиться, и набор уровней может исчезнуть через несколько временных шагов. Поэтому часто требуются конечно-разностные схемы высокого порядка, такие как практически неколебательные (ENO) схемы высокого порядка, и даже в этом случае осуществимость долгосрочного моделирования сомнительна. Для преодоления этой проблемы были разработаны более продвинутые методы; например, комбинации метода нивелирования с отслеживанием частиц-маркеров, подсказанные полем скоростей. ^[4]

Пример

Рассмотрим единичный круг в ${\textstyle \mathbb {R} ^{2}}$ , сжимаясь с постоянной скоростью, т. е. каждая точка на границе круга движется вдоль его внутренней части, указывая обычно с некоторой фиксированной скоростью. Круг сожмется и в конечном итоге схлопнется до точки. Если исходное поле расстояний построено (т. е. функция, значением которой является знаковое евклидово расстояние до границы, положительное внутреннее, отрицательное внешнее) на исходной окружности, то нормализованный градиент этого поля будет нормалью окружности.

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

Приложения

В математическом моделировании горения LSM используется для описания мгновенной поверхности пламени, известной как G. уравнение
Структуры данных с набором уровней были разработаны для облегчения использования метода набора уровней в компьютерных приложениях.
Вычислительная гидродинамика
Планирование траектории
Оптимизация
Обработка изображений
Вычислительная биофизика
Дискретная сложная динамика (визуализация плоскости параметров и динамической плоскости )

История

Метод набора уровней был разработан в 1979 году Аленом Дервье. ^[5] и впоследствии популяризированный Стэнли Ошером и Джеймсом Сетианом . С тех пор он стал популярен во многих дисциплинах, таких как обработка изображений , компьютерная графика , вычислительная геометрия , оптимизация , вычислительная гидродинамика и вычислительная биология .

См. также

Ссылки

^ Ошер, С.; Сетиан, Дж. А. (1988), «Фронты, распространяющиеся со скоростью, зависящей от кривизны: алгоритмы, основанные на формулировках Гамильтона – Якоби» (PDF) , J. Comput. Физ. , 79 (1): 12–49, Бибкод : 1988JCoPh..79...12O , CiteSeerX 10.1.1.46.1266 , doi : 10.1016/0021-9991(88)90002-2 , hdl : 10338.dmlcz/144762 , S2CID 205007680
^ Jump up to: ^а ^б Ошер, Стэнли Дж .; Федкив, Рональд П. (2002). Методы набора уровней и динамические неявные поверхности . Спрингер-Верлаг . ISBN 978-0-387-95482-0 .
^ Jump up to: ^а ^б Сетиан, Джеймс А. (1999). Методы набора уровней и методы быстрого марша: развивающиеся интерфейсы в вычислительной геометрии, механике жидкости, компьютерном зрении и материаловедении . Издательство Кембриджского университета . ISBN 978-0-521-64557-7 .
^ Энрайт, Д.; Федкив, Р.П.; Ферцигер, Дж. Х. ; Митчелл, И. (2002), «Метод набора гибридных уровней частиц для улучшенного захвата интерфейса» (PDF) , J. Comput. Физ. , 183 (1): 83–116, Bibcode : 2002JCoPh.183...83E , CiteSeerX 10.1.1.15.910 , doi : 10.1006/jcph.2002.7166
^ Дервье, А.; Томассет, Ф. (1980). «Метод конечных элементов для моделирования неустойчивости Рэлея-Тейлора». Методы аппроксимации задач Навье-Стокса . Конспект лекций по математике. Том. 771. Спрингер. стр. 145–158. дои : 10.1007/BFb0086904 . ISBN 978-3-540-38550-9 .

Внешние ссылки

Посетите Рональда Федкива , академическую веб-страницу где представлено множество изображений и анимаций, показывающих, как метод набора уровней можно использовать для моделирования явлений реальной жизни.
Multivac — это библиотека C++ для отслеживания фронта в 2D с помощью методов установки уровней.
Джеймса Сетиана, посвященная Веб-страница методу набора уровней.
Стэнли Ошера Домашняя страница .
Метод установки уровней. МИТ 16,920Дж/2,097Дж/6,339Дж. Численные методы для уравнений в частных производных Пер-Улофа Перссона. 8 марта 2005 г.
Лекция 11: Метод установки уровней: MIT 18.086. Математические методы для инженеров II Гилберта Стрэнга

[1] Ошер, С.; Сетиан, Дж. А. (1988), «Фронты, распространяющиеся со скоростью, зависящей от кривизны: алгоритмы, основанные на формулировках Гамильтона – Якоби» (PDF) , J. Comput. Физ. , 79 (1): 12–49, Бибкод : 1988JCoPh..79...12O , CiteSeerX 10.1.1.46.1266 , doi : 10.1016/0021-9991(88)90002-2 , hdl : 10338.dmlcz/144762 , S2CID 205007680

[osher-2] Jump up to: ^а ^б Ошер, Стэнли Дж .; Федкив, Рональд П. (2002). Методы набора уровней и динамические неявные поверхности . Спрингер-Верлаг . ISBN 978-0-387-95482-0 .

[sethian-3] Jump up to: ^а ^б Сетиан, Джеймс А. (1999). Методы набора уровней и методы быстрого марша: развивающиеся интерфейсы в вычислительной геометрии, механике жидкости, компьютерном зрении и материаловедении . Издательство Кембриджского университета . ISBN 978-0-521-64557-7 .

[4] Энрайт, Д.; Федкив, Р.П.; Ферцигер, Дж. Х. ; Митчелл, И. (2002), «Метод набора гибридных уровней частиц для улучшенного захвата интерфейса» (PDF) , J. Comput. Физ. , 183 (1): 83–116, Bibcode : 2002JCoPh.183...83E , CiteSeerX 10.1.1.15.910 , doi : 10.1006/jcph.2002.7166

[5] Дервье, А.; Томассет, Ф. (1980). «Метод конечных элементов для моделирования неустойчивости Рэлея-Тейлора». Методы аппроксимации задач Навье-Стокса . Конспект лекций по математике. Том. 771. Спрингер. стр. 145–158. дои : 10.1007/BFb0086904 . ISBN 978-3-540-38550-9 .

[1]

[2]

[3]

[4]

[5]