Функция расстояния со знаком

Расстояние от точки до границы множества

График (внизу, красным цветом) знакового расстояния между точками на плоскости xy (синим цветом) и неподвижным диском ( также представленным сверху, серым цветом)

Более сложный набор (вверху) и график его функции знакового расстояния (внизу, красным).

В математике и ее приложениях функция знакового расстояния или поле знакового расстояния ( SDF ) — это ортогональное расстояние заданной точки x до границы множества Ω в метрическом пространстве (например, поверхности геометрической фигуры), причем знак определяется тем, находится ли x внутри Ω или нет . Функция имеет положительные значения в точках x внутри Ω, она уменьшается по значению, когда x приближается к границе Ω, где функция знакового расстояния равна нулю, и принимает отрицательные значения вне Ω. ^[1] Однако иногда вместо этого принимается и альтернативное соглашение (то есть отрицательно внутри Ω и положительно снаружи). ^[2] Эта концепция также иногда называется ориентированной функцией/полем расстояния .

Определение

Пусть Ω — подмножество метрического пространства X с метрикой d , а — его граница . Расстояние между точкой x пространства X и подмножеством X определяется, как обычно, как ${\displaystyle \partial \Omega }$ ${\displaystyle \partial \Omega }$

${\displaystyle d(x,\partial \Omega )=\inf _{y\in \partial \Omega }d(x,y),}$

где обозначает нижнюю грань . ${\displaystyle \inf }$

Функция расстояния со знаком от точки x до X определяется как ${\displaystyle \Omega }$

${\displaystyle f(x)={\begin{cases}d(x,\partial \Omega )&{\text{if }}x\in \Omega \\-d(x,\partial \Omega )&{\text{if }}\,x\notin \Omega .\end{cases}}}$

Свойства в евклидовом пространстве

Если Ω — подмножество евклидова пространства Rn с кусочно- гладкой границей, то функция знакового расстояния дифференцируема почти всюду , а ее ^{градиент} удовлетворяет уравнению эйконала

${\displaystyle |\nabla f|=1.}$

Если граница Ω равна C ^k для k ≥ 2 (см. Классы дифференцируемости ), то d равна C ^k в точках, достаточно близких к границе Ω. ^[3] В частности, на границе f удовлетворяет

${\displaystyle \nabla f(x)=N(x),}$

где N — векторное поле внутренней нормали . Таким образом, функция расстояния со знаком является дифференцируемым расширением векторного поля нормы. В частности, гессиан функции расстояния со знаком на границе Ω дает отображение Вайнгартена .

Если, далее, Γ — область, достаточно близкая к границе Ω, так что f дважды непрерывно дифференцируема на ней, то существует явная формула, включающая отображение Вайнгартена W _x для якобиана изменяющихся переменных в терминах функции расстояния со знаком и ближайшей граничной точки. В частности, если T ( ∂ Ω, μ ) — множество точек в пределах расстояния μ от границы Ω (т. е. трубчатая окрестность радиуса μ ), а g — абсолютно интегрируемая функция на Γ, то

${\displaystyle \int _{T(\partial \Omega ,\mu )}g(x)\,dx=\int _{\partial \Omega }\int _{-\mu }^{\mu }g(u+\lambda N(u))\,\det(I-\lambda W_{u})\,d\lambda \,dS_{u},}$

где det обозначает определитель , а dS _u указывает на то, что мы берем поверхностный интеграл . ^[4]

Алгоритмы

Алгоритмы для вычисления функции расстояния со знаком включают эффективный быстрый метод маршировки , быстрый метод подметания ^[5] и более общий метод набора уровней .

Для воксельного рендеринга быстрый алгоритм расчета SDF в геометрии такси использует таблицы суммированных площадей . ^[6]

Приложения

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

Функции расстояния со знаком применяются, например, при рендеринге в реальном времени , ^[7] например, метод SDF-проецирования лучей и компьютерное зрение . ^{[8] [9]}

SDF использовался для описания геометрии объектов при рендеринге в реальном времени , обычно в контексте raymarching, начиная с середины 2000-х годов. К 2007 году Valve использовала SDF для рендеринга больших пиксельных (или с высоким DPI ) гладких шрифтов с ускорением GPU в своих играх. ^[10] Метод Valve не идеален, поскольку он работает в растровом пространстве , чтобы избежать вычислительной сложности решения проблемы в (непрерывном) векторном пространстве. Отображенный текст часто теряет острые углы. В 2014 году улучшенный метод был представлен Бехдадом Эсфахбодом . GLyphy Бехдада аппроксимирует кривые Безье шрифта с помощью дуговых сплайнов, ускоренных методами дискретизации на основе сетки (которые отбрасывают слишком далекие точки) для работы в реальном времени. ^[11]

Модифицированная версия SDF была введена как функция потерь для минимизации ошибки взаимопроникновения пикселей при рендеринге нескольких объектов. ^[12] В частности, для любого пикселя, который не принадлежит объекту, если он находится за пределами объекта при рендеринге, штраф не налагается; если это так, налагается положительное значение, пропорциональное его расстоянию внутри объекта.

${\displaystyle f(x)={\begin{cases}0&{\text{if }}\,x\in \Omega ^{c}\\d(x,\partial \Omega )&{\text{if }}\,x\in \Omega \end{cases}}}$

В 2020 году игровой движок FOSS Godot 4.0 получил глобальное освещение в реальном времени (SDFGI) на основе SDF, что стало компромиссом между более реалистичным воксельным GI и запеченным GI. Его основное преимущество заключается в том, что его можно применять к бесконечному пространству, что позволяет разработчикам использовать его для игр с открытым миром. ^[13]

В 2023 году был выпущен фреймворк пользовательского интерфейса "GPUI" для рисования всех элементов пользовательского интерфейса с использованием графического процессора, многие части с использованием SDF. Автор утверждает, что создал редактор кода Zed , который выполняет рендеринг со скоростью 120 кадров в секунду. В работе используются список геометрических примитивов Иниго Куилеза в SDF, аппроксимированное гауссово размытие Эвана Уоллеса (соучредителя Figma ) в SDF и новый скругленный прямоугольник SDF. ^[14]

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

• Функция расстояния
• Метод установки уровня
• Уравнение Эйконала
• Параллельная кривая (также известная как смещенная кривая)
• Длина дуги со знаком
• Подписанная область
• Подписанная мера
• Подписанный том

Примечания

1. Чан, Т.; Чжу, В. (2005). Априорная сегментация формы на основе набора уровней . Конференция компьютерного общества IEEE по компьютерному зрению и распознаванию образов. doi :10.1109/CVPR.2005.212.
2. Malladi, R.; Sethian, JA; Vemuri, BC (1995). «Моделирование формы с фронтальным распространением: подход с использованием набора уровней». Труды IEEE по анализу шаблонов и машинному интеллекту . 17 (2): 158–175. CiteSeerX 10.1.1.33.2443 . doi :10.1109/34.368173. S2CID  9505101. 
3. Гилбарг и Трудингер 1983, Лемма 14.16.
4. Гилбарг и Трудингер 1983, Уравнение (14.98).
5. Чжао Хункай . Быстрый метод подметания для уравнений эйконала. Математика вычислений, 2005, 74. Jg., Nr. 250, S. 603-627.
6. Нильссон, Тобиас (2019). «Методы оптимизации прямого объемного рендеринга в клиентской сети» (PDF) . Цифровой Ветенскаплига Аркивет . Проверено 8 июля 2022 г.
7. Томас Акенин-Мёллер; Эрик Хейнс; Нати Хоффман (6 августа 2018 г.). Рендеринг в реальном времени, четвертое издание. CRC Press. ISBN 978-1-351-81615-1.
8. Перера, С.; Барнс, Н.; Хе, X.; Изади, С.; Кохли, П.; Глокер, Б. (январь 2015 г.). «Сегментация движения объемных поверхностей на основе усеченной знаковой функции расстояния». Зимняя конференция IEEE 2015 г. по приложениям компьютерного зрения . стр. 1046–1053. doi :10.1109/WACV.2015.144. ISBN 978-1-4799-6683-7. S2CID  16811314.
9. Изади, Шахрам; Ким, Дэвид; Хиллиджес, Отмар; Молино, Дэвид; Ньюкомб, Ричард; Кохли, Пушмит; Шоттон, Джейми; Ходжес, Стив; Фримен, Дастин (2011). "KinectFusion". Труды 24-го ежегодного симпозиума ACM по программному обеспечению и технологиям пользовательского интерфейса . UIST '11. Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 559–568. doi :10.1145/2047196.2047270. ISBN 9781450307161. S2CID  3345516.
10. Грин, Крис (2007). «Улучшенное альфа-тестированное увеличение для векторных текстур и спецэффектов». Курсы ACM SIGGRAPH 2007. стр. 9–18. CiteSeerX 10.1.1.170.9418 . doi :10.1145/1281500.1281665. ISBN  9781450318235. S2CID  7479538.
11. Бехдад Эсфахбод. GLyphy: высококачественная визуализация глифов с использованием шейдеров OpenGL ES2 [linux.conf.au 2014]. YouTube . Архивировано из оригинала 2021-12-11.Исходный код
12. Цзян, Вэнь; Колотурос, Никос; Павлакос, Георгиос; Чжоу, Сяовэй; Даниилидис, Костас (15.06.2020). «Последовательная реконструкция нескольких людей по одному изображению». arXiv : 2006.08586 [cs.CV].
13. Движок, Godot. "Godot 4.0 получает глобальное освещение в реальном времени на основе SDF". Godot Engine .
14. Scandurra, Antonio (7 марта 2023 г.). «Использование Rust и GPU для рендеринга пользовательских интерфейсов со скоростью 120 кадров в секунду — блог Zed». Zed .

Ссылки

• Стэнли Дж. Ошер и Рональд П. Федкив (2003). Методы набора уровней и динамические неявные поверхности. Springer. ISBN 9780387227467.
• Гилбарг, Д.; Трудингер, Н.С. (1983). Эллиптические уравнения в частных производных второго порядка . Grundlehren der mathematischen Wissenschaften. Том. 224 (2-е изд.). Спрингер-Верлаг.(или Приложение к 1-му изданию 1977 г.)