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

Графік (внизу, червоним кольором) відстані зі знаком між точками площини $xy$ (синім кольором) та круга (показаного вгорі, сірим кольором)

Складніша множина (вгорі) та графік її функції відстані зі знаком (унизу, червоним кольором)

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

Визначення

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

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

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

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

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

Властивості в евклідовому просторі

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

$|\nabla f|=1.$

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

$\nabla f(x)=N(x),$

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

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

$\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}$ вказує на те, що ми беремо поверхневий інтеграл.

Алгоритми

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

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

Застосування

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

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

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

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

$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), яке стало компромісом між реалістичнішим воксельним ГО та запеченим ГО. Його основна перевага в тому, що його можна застосовувати в нескінченному просторі. Це дає змогу розробникам використовувати його для ігор з відкритим світом.

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

Див. також

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

Посилання

• 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 року)