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

Концептуальная основа, используемая в численном анализе поверхностей и форм

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

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

Иллюстрация метода установки уровня

Обзор

Рисунок справа иллюстрирует несколько идей о LSM. В верхнем левом углу находится ограниченная область с хорошо ведущей себя границей. Под ней красная поверхность — график функции уровня, определяющей эту форму, а плоская синяя область представляет плоскость XY . Граница формы тогда является множеством нулевого уровня , в то время как сама форма — это множество точек на плоскости, для которых положительно (внутри формы) или равно нулю (на границе). ${\displaystyle \varphi }$ ${\displaystyle \varphi }$ ${\displaystyle \varphi }$

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

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

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

и метод level-set неявно манипулирует через функцию . Предполагается, что эта функция принимает положительные значения внутри области, ограниченной кривой, и отрицательные значения снаружи. ^{[2] [3]} ${\displaystyle \Gamma }$ ${\displaystyle \varphi }$ ${\displaystyle \varphi }$ ${\displaystyle \Gamma }$

Уравнение уровня

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

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

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

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

Пример

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

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

Приложения

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

История

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

Смотрите также

• Контурная диаграмма
• Анализ зебры
• Уравнение G
• Расширенная библиотека моделирования
• Метод объема жидкости
• Сегментация изображения#Методы установки уровня
• Методы погруженных границ
• Стохастические эйлеровы лагранжевы методы
• Уровень набора (структуры данных)
• Постеризация

Ссылки

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

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

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