Функція відстані зі знаком

У математиці та її застосуваннях, функція відстані зі знаком або поле відстані зі знаком (ПВЗ; англ. SDF — signed distance field) — ортогональна відстань від заданої точки ${\displaystyle x}$ до межі множини ${\displaystyle \Omega }$ в метричному просторі (наприклад, поверхні геометричної фігури), причому знак визначається тим, чи міститься ${\displaystyle x}$ усередині ${\displaystyle \Omega }$. Функція має додатні значення в точках ${\displaystyle x}$ усередині ${\displaystyle \Omega }$, її значення зменшується, коли ${\displaystyle x}$ наближається до межі ${\displaystyle \Omega }$, де функція відстані зі знаком дорівнює нулю, і набуває від'ємних значень поза ${\displaystyle \Omega }$.^[1] Однак іноді замість цього використовують протилежну домовленість (тобто від'ємні значення всередині ${\displaystyle \Omega }$ та додатні зовні).^[2] Цю концепцію також іноді називають орієнтованою функцією/полем відстані.

Нехай ${\displaystyle \Omega }$ — підмножина метричного простору X із метрикою d, а ${\displaystyle \partial \Omega }$ — її межа. Відстань між точкою ${\displaystyle x}$ із X та підмножиною X ${\displaystyle \partial \Omega }$ визначають, як

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

де ${\displaystyle \inf }$ позначає інфімум.

Функцію відстані зі знаком від точки ${\displaystyle x}$ із X до ${\displaystyle \Omega }$ визначають як

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

Якщо ${\displaystyle \Omega }$ — підмножина евклідового простору Rⁿ з кусково-гладкою межею, то функція відстані зі знаком диференційовна майже скрізь, а її градієнт задовольняє рівняння ейконалу

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

Якщо межа ${\displaystyle \Omega }$ є ${\displaystyle C^{k}}$ для ${\displaystyle k\geqslant 2}$ (див. Класи диференційовності), то ${\displaystyle d}$ є ${\displaystyle C^{k}}$ в точках, достатньо близьких до межі ${\displaystyle \Omega }$.^[3] Зокрема, на межі ${\displaystyle f}$ задовольняє умову

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

де N — векторне поле нормалей внутрішньої ділянки. Таким чином, функція відстані зі знаком є диференційовним розширенням поля нормалей. Зокрема, гессіан функції відстані зі знаком на межі ${\displaystyle \Omega }$ дає відображення Вайнгартена.

Якщо, далі, ${\displaystyle \Gamma }$ — це ділянка, достатньо близька до межі ${\displaystyle \Omega }$, така що ${\displaystyle f}$ є двічі неперервно диференційовною на ній, то існує явна формула, що включає відображення Вайнгартена ${\displaystyle W_{x}}$ для якобіана змінюваних змінних через функцію відстані зі знаком та найближчу точку межі. Зокрема, якщо ${\displaystyle T(\partial \Omega ,\mu )}$ — множина точок на відстані ${\displaystyle \mu }$ від межі ${\displaystyle \Omega }$ (тобто трубчастого околу радіуса ${\displaystyle \mu }$), а ${\displaystyle g}$ — абсолютно інтегровна функція^[en] на ${\displaystyle \Gamma }$, то

${\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 позначає визначник, а ${\displaystyle dS_{u}}$ вказує на те, що ми беремо поверхневий інтеграл.^[4]

Алгоритми для обчислення функції відстані зі знаком включають ефективний метод швидкого крокування^[en], метод швидкого прибирання^[en] та загальніший метод установлення рівнів^[en].

Для воксельного рендерингу швидкий алгоритм обчислення ПВЗ в мангеттенській метриці використовує таблиці сумарних площ.^[5]

Функції відстані зі знаком застосовують, наприклад, для рендерингу в реальному часі,^[6] зокрема, в методі ПВЗ-маршування променів^[en], та в комп'ютерному зорі.^[7][8]

ПВЗ використовують для опису геометрії об'єктів у режимі реального часу, зазвичай у контексті маршування променів, починаючи від середини 2000-х років. 2007 року Valve використовувала ПЗВ для рендерингу гладких шрифтів^[en] за великого розміру пікселів (або високої роздільності) в іграх із прискоренням ГП.^[9] Метод Valve не ідеальний, оскільки працює в растровому просторі, щоб уникнути обчислювальної складності розв'язання задачі в (неперервному) векторному просторі. Відрендерений текст часто втрачає гострі кути. 2014 року Бегдад Есфагбод^[en] представив удосконалений метод. GLyphy Бегдада апроксимує криві Безьє шрифту за допомогою дугових сплайнів, із прискоренням методами дискретизації на основі сітки (які відсікають занадто віддалені точки) для роботи в режимі реального часу.^[10]

Модифіковану версію ПВЗ введено як функцію втрат для мінімізації помилки взаємопроникнення пікселів під час візуалізації кількох об'єктів.^[11] Зокрема, для будь-якого пікселя, який не належить об'єкту, якщо він лежить поза об'єктом відтворення, поправка не робиться; якщо ж належить, то застосовується додатне значення, пропорційне його відстані всередині об'єкта.

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

2020 року у вільному ігровому рушії Godot 4.0 з'явилося глобальне освітлення в реальному часі на основі ПВЗ (ПВЗГО; англ. SDFGI — SDF-based global illumination), яке стало компромісом між реалістичнішим воксельним ГО та запеченим ГО. Його основна перевага в тому, що його можна застосовувати в нескінченному просторі. Це дає змогу розробникам використовувати його для ігор з відкритим світом.^[12]

2023 року автори текстового редактора Zed анонсували фреймворк GPUI, який малює всі елементи інтерфейсу користувача за допомогою графічного процесора зі швидкістю 120 кадрів на секунду. У роботі використано список геометричних примітивів Іньїго Кілеса (Inigo Quilez) в ПВЗ, гауссове згладжування в ПВЗ співзасновника Figma Евана Воллеса (Evan Wallace) та нове ПВЗ із закругленими прямокутниками.^[13]

• Метричний простір
• Ейконал
• Паралельна крива (також відома як зміщена крива)
• Площа зі знаком^[en]
• Заряд (теорія міри)
• Мішаний добуток

• Stanley J. Osher and Ronald P. Fedkiw (2003). Level Set Methods and Dynamic Implicit Surfaces. Springer. ISBN 9780387227467.
• Gilbarg, D.; Trudinger, N. S. (1983). Elliptic Partial Differential Equations of Second Order. Grundlehren der mathematischen Wissenschaften. Т. 224 (вид. 2nd). Springer-Verlag. (або додаток до 1-го видання 1977 року)