Набор уровней (структуры данных)

В информатике набора уровней структура данных предназначена для представления с дискретной выборкой функций динамических наборов уровней .

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

Хронологические события

Мощный метод установки уровней принадлежит Ошеру и Сетиану , 1988. Однако простая реализация через плотный d-мерный массив значений приводит к усложнению как времени, так и хранения. $O(n^{d})$, где $n$ - поперечное разрешение пространственных размеров домена и $d$ – количество пространственных измерений области.

Узкая полоса

Метод узкополосного набора уровней, предложенный в 1995 году Адалстейнссоном и Сетианом: ограничил большинство вычислений тонкой полосой активных вокселей, непосредственно окружающих интерфейс, тем самым уменьшив временную сложность в трех измерениях до $O(n^{2})$ для большинства операций. Требовалось периодическое обновление узкополосной структуры для восстановления списка активных вокселов, что повлекло за собой $O(n^{3})$ операция, при которой осуществлялся доступ к вокселам по всему объему. Сложность хранения для этой узкополосной схемы все еще была $O(n^{3}).$ Дифференциальные конструкции на краю узкозонной области требуют тщательной интерполяции и схем изменения области для стабилизации решения.

Редкое поле

Этот $O(n^{3})$ временная сложность была устранена в приближенном методе набора уровней «разреженного поля», представленном Уитакером в 1998 году. Метод набора разреженных полей использует набор связанных списков для отслеживания активных вокселов вокруг интерфейса. Это позволяет постепенно расширять активную область по мере необходимости без каких-либо значительных накладных расходов. Хотя последовательно $O(n^{2})$ эффективен во времени, $O(n^{3})$ Для метода набора уровней разреженных полей по-прежнему требуется место для хранения. Видеть для получения подробной информации о реализации.

Разреженная сетка блоков

Метод разреженной блочной сетки, предложенный Бридсоном в 2003 году, делит весь ограничивающий объем размера $n^{3}$ на небольшие кубические блоки $m^{3}$ вокселей каждый. Крупная сетка размером $(n/m)^{3}$ затем сохраняет указатели только на те блоки, которые пересекают узкую полосу набора уровней. Распределение и освобождение блоков происходят по мере распространения поверхности, чтобы приспособиться к деформациям. Этот метод имеет неоптимальную сложность хранения $O\left((nm)3+m^{3}n^{2}\right)$, но сохраняет доступ к постоянному времени, присущий плотным сеткам.

Октри

Метод набора уровней октодерева , представленный Стрейном в 1999 году. и усовершенствован Лосассо, Гибу и Федкивом, и совсем недавно Мин и Гибу использует дерево вложенных кубов, конечные узлы которого содержат значения расстояний со знаком. Наборы уровней октодерева в настоящее время требуют равномерного уточнения вдоль интерфейса (т.е. узкой полосы), чтобы получить достаточную точность. Это представление эффективно с точки зрения хранения, $O(n^{2}),$ и относительно эффективен с точки зрения запросов доступа, $O(\log \,n).$ Преимущество метода уровней для структур данных октодерева состоит в том, что можно решать уравнения в частных производных, связанные с типичными задачами со свободными границами, в которых используется метод набора уровней. Исследовательская группа CASL разработал это направление работы в области вычислительных материалов, вычислительной гидродинамики, электрокинетики, хирургии с визуальным контролем и средств управления.

Закодировано по длине серии

Метод набора уровней кодирования длин серий (RLE), представленный в 2004 году, применяет схему RLE для сжатия областей из узкой полосы до их знакового представления, сохраняя при этом с полной точностью узкую полосу. Последовательное прохождение узкой полосы является оптимальным, а эффективность хранения еще больше повышается по сравнению с набором уровней октодерева. Добавление таблицы ускорения позволяет быстро $O(\log r)$ произвольный доступ, где r — количество проходов на сечение. Дополнительная эффективность достигается за счет применения схемы RLE в размерной рекурсии - метода, представленного в аналогичной DT-Grid компании Nielsen & Museth.

Набор локального уровня хэш-таблицы

Метод набора локального уровня хэш-таблицы, представленный в 2011 году Эйиюрекли и Брином. и расширен в 2012 году Брюном, Гитте и Гибу, только вычисляет данные набора уровней в полосе вокруг интерфейса, как в методе узкополосного набора уровней, но также сохраняет данные только в той же полосе. Используется структура данных хеш-таблицы, которая обеспечивает $O(1)$ доступ к данным. Однако Брун и др. пришли к выводу, что их метод, хотя и проще в реализации, работает хуже, чем реализация квадродерева. Они находят это

как бы то ни было, [...] структура данных квадродерева кажется более адаптированной, чем структура данных хеш-таблицы для алгоритмов с набором уровней.

Перечислены три основные причины снижения эффективности:

1. для получения точных результатов необходима достаточно большая полоса вблизи границы раздела, что уравновешивает отсутствие узлов сетки вдали от границы раздела;
2. производительность ухудшается из-за процедур экстраполяции на внешних краях локальной сетки и
3. ширина полосы ограничивает шаг по времени и замедляет метод.

На основе точек

Корбетт в 2005 году представил метод установки уровня на основе точек. Вместо использования однородной выборки набора уровней непрерывная функция набора уровней восстанавливается из набора неорганизованных точечных выборок посредством перемещения по методу наименьших квадратов .