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

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

Определение

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

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{if }}x\in \Omega \\-d(x,\partial \Omega )&{\text{if }}\,x\notin \Omega .\end{cases}}

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

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

|\nabla f|=1.

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

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

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

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

\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 для рендеринга гладких шрифтов с ускорением графического процессора в своих играх. ^{[ 10 ]} Метод Valve не идеален, поскольку он работает в растровом пространстве , чтобы избежать вычислительной сложности решения проблемы в (непрерывном) векторном пространстве. Отрисованный текст часто теряет острые углы. В 2014 году улучшенный метод представил Бехдад Исфабод . шрифта GLyphy Бехдада аппроксимирует кривые Безье дуговыми сплайнами, ускоренными с помощью методов дискретизации на основе сетки (которые отбирают слишком удаленные точки) для работы в реальном времени. ^{[ 11 ]}

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

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 в реальном времени на основе SDF получил глобальное освещение (SDFGI), что стало компромиссом между более реалистичным GI на основе вокселей и запеченным GI. Его основное преимущество заключается в том, что его можно применять к бесконечному пространству, что позволяет разработчикам использовать его для игр с открытым миром. ^{[ 13 ]}

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

См. также

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

Примечания

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

Ссылки

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

[1] Чан, Т.; Чжу, В. (2005). Предварительная сегментация формы на основе набора уровней . Конференция IEEE Computer Society по компьютерному зрению и распознаванию образов. дои : 10.1109/CVPR.2005.212 .

[2] Маллади, Р.; Сетиан, Дж.А.; Вемури, Британская Колумбия (1995). «Моделирование формы с распространением фронта: подход с набором уровней». Транзакции IEEE по анализу шаблонов и машинному интеллекту . 17 (2): 158–175. CiteSeerX 10.1.1.33.2443 . дои : 10.1109/34.368173 . S2CID 9505101 .

[FOOTNOTEGilbargTrudinger1983Lemma_14.16-3] Гилбарг и Трудингер 1983 , Лемма 14.16.

[FOOTNOTEGilbargTrudinger1983Equation_(14.98)-4] Гилбарг и Трудингер 1983 , Уравнение (14.98).

[5] Чжао Хункай . Метод быстрой прогонки для уравнений эйконала . Математика вычислений, 2005, 74. Jg., Nr. 250, С. 603-627.

[6] Нильссон, Тобиас (2019). «Методы оптимизации прямого объемного рендеринга в клиентской сети» (PDF) . Цифровой научный архив . Проверено 8 июля 2022 г.

[̈llerHaines2018-7] Томас Акенин-Мёллер; Эрик Хейнс; Нати Хоффман (6 августа 2018 г.). Рендеринг в реальном времени, четвертое издание . ЦРК Пресс. ISBN 978-1-351-81615-1 .

[8] Перера, С.; Барнс, Н.; Он, Х.; Изади, С.; Кохли, П.; Глокер, Б. (январь 2015 г.). «Сегментация движения объемных поверхностей с усеченной знаковой функцией расстояния на основе функции расстояния». Зимняя конференция IEEE 2015 по приложениям компьютерного зрения . стр. 1046–1053. дои : 10.1109/WACV.2015.144 . ISBN 978-1-4799-6683-7 . S2CID 16811314 .

[9] Изади, Шахрам; Ким, Дэвид; Хиллигес, Отмар; Молино, Дэвид; Ньюкомб, Ричард; Кохли, Пушмит; Шоттон, Джейми; Ходжес, Стив; Фриман, Дастин (2011). «КинектФьюжн». Материалы 24-го ежегодного симпозиума ACM по программному обеспечению и технологиям пользовательского интерфейса . УИСТ '11. Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 559–568. дои : 10.1145/2047196.2047270 . ISBN 9781450307161 . S2CID 3345516 .

[10] Грин, Крис (2007). «Улучшенное увеличение векторных текстур и спецэффектов при альфа-тестировании». Курсы ACM SIGGRAPH 2007 . стр. 9–18. CiteSeerX 10.1.1.170.9418 . дои : 10.1145/1281500.1281665 . ISBN 9781450318235 . S2CID 7479538 .

[11] Бехдад Исфабод. GLyphy: высококачественный рендеринг глифов с использованием шейдеров OpenGL ES2 [linux.conf.au 2014] . Ютуб . Архивировано из оригинала 11 декабря 2021 г. Исходный код

[12] Цзян, Вэнь; Колотурос, Никос; Павлакос, Георгиос; Чжоу, Сяовэй; Данилидис, Костас (15 июня 2020 г.). «Последовательная реконструкция нескольких людей по одному изображению». arXiv : 2006.08586 [ cs.CV ].

[13] Двигатель, Годо. «Godot 4.0 получает глобальное освещение в реальном времени на основе SDF» . Двигатель Годо .

[14] Скандурра, Антонио (7 марта 2023 г.). «Использование Rust и графического процессора для рендеринга пользовательских интерфейсов со скоростью 120 кадров в секунду — блог Zed» . Зед .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]