Знаковая функция расстояния - Signed distance function

Диск (вверху, серый) и его функция расстояния со знаком (внизу, красный). В Икс-у самолет показан синим цветом.

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

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

Определение

Если Ω является подмножеством метрическое пространство, Икс, с метрикой, d, то знаковая функция расстояния, ж, определяется

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

куда ${\displaystyle \partial \Omega }$ обозначает граница из ${\displaystyle \Omega }$. Для любого ${\displaystyle x\in X}$,

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

куда инф обозначает инфимум.

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

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

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

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

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

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

Если, далее, Γ - область, достаточно близкая к границе Ω который ж дважды непрерывно дифференцируемо на нем, то существует явная формула, включающая отображение Вейнгартена W_Икс для якобиана изменяющихся переменных в терминах функции расстояния со знаком и ближайшей граничной точки. В частности, если Т(∂Ω,μ) - это множество точек на расстоянии μ границы Ω (т.е. трубчатый район радиуса μ), и грамм является абсолютно интегрируемой функцией на Γ, тогда

${\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_ты указывает на то, что мы берем поверхностный интеграл.^[4]

Алгоритмы

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

Приложения

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

Знаковые функции расстояния применяются, например, в рендеринг в реальном времени^[6] и компьютерное зрение.^[7][8]

Они также использовались в методе (разработанном Клапан ) для рендеринга гладкие шрифты в больших размерах (или альтернативно в высокий DPI ) с помощью GPU ускорение.^[9] Метод Valve вычислен со знаком поля расстояний в растровое пространство во избежание вычислительной сложности решения задачи в (непрерывном) векторном пространстве. Совсем недавно были предложены решения для кусочно-аппроксимации (которые, например, аппроксимируют кривую Безье с помощью дуговых сплайнов), но даже в этом случае вычисления могут быть слишком медленными для рендеринг в реальном времени, и ему должны помогать сеточные дискретизация методы для аппроксимации (и исключения из вычислений) расстояния до точек, которые находятся слишком далеко.^[10]

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

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

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

Примечания

1. Чан, Т .; Чжу, В. (2005). Предварительная сегментация формы на основе набора уровней. Конференция компьютерного общества IEEE по компьютерному зрению и распознаванию образов. Дои:10.1109 / CVPR.2005.212.
2. Malladi, R .; Sethian, J.A .; Вемури, до н.э. (1995). «Моделирование формы с фронтальным распространением: подход с помощью набора уровней». IEEE Transactions по анализу шаблонов и машинному анализу. 17 (2): 158–175. CiteSeerX  10.1.1.33.2443. Дои:10.1109/34.368173.
3. Гилбарг 1983, Лемма 14.16. Ошибка sfn: цель отсутствует: CITEREFGilbarg1983 (помощь)
4. Гилбарг 1983, Уравнение (14.98). Ошибка sfn: цель отсутствует: CITEREFGilbarg1983 (помощь)
5. Чжао Хункай. Метод быстрого поиска для уравнений эйконала. Математика вычислений, 2005, 74. Jg., Nr. 250, С. 603-627.
6. Томас Акенин-Мёллер; Эрик Хейнс; Нати Хоффман (6 августа 2018 г.). Рендеринг в реальном времени, четвертое издание. CRC Press. ISBN  978-1-351-81615-1.
7. Perera, S .; Barnes, N .; Он, X .; Изади, С .; Коли, П .; Глокер, Б. (январь 2015 г.). «Сегментация движения объемных поверхностей на основе усеченной функции расстояния со знаком». 2015 Зимняя конференция IEEE по приложениям компьютерного зрения: 1046–1053. Дои:10.1109 / WACV.2015.144. ISBN  978-1-4799-6683-7. S2CID  16811314.
8. Изади, Шахрам; Ким, Дэвид; Хиллигес, Отмар; Молино, Дэвид; Ньюкомб, Ричард; Коли, Пушмит; Шоттон, Джейми; Ходжес, Стив; Фриман, Дастин (2011). «KinectFusion: 3D-реконструкция и взаимодействие в реальном времени с помощью движущейся камеры определения глубины». Материалы 24-го ежегодного симпозиума ACM по программному обеспечению и технологиям пользовательского интерфейса. УИСТ '11. Нью-Йорк, Нью-Йорк, США: ACM: 559–568. Дои:10.1145/2047196.2047270. ISBN  9781450307161. S2CID  3345516.
9. Грин, Крис (2007). «Улучшено увеличение при альфа-тестировании векторных текстур и спецэффектов». ACM SIGGRAPH 2007 Курсы на - SIGGRAPH '07. п. 9. CiteSeerX  10.1.1.170.9418. Дои:10.1145/1281500.1281665. ISBN  9781450318235. S2CID  7479538. Отсутствует или пусто | название = (помощь)
10. https://www.youtube.com/watch?v=7tHv6mcIIeo

Рекомендации

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