В математике и ее приложениях функция расстояния со знаком (или ориентированная функция расстояния ) множества Ω в метрическом пространстве определяет расстояние данной точки x от границы Ω, причем знак определяется тем, находится ли x в Ω. Функция имеет положительные значения в точках х внутри Q, она уменьшается в цене , как х приближается к границе Q , где подписанная функция расстояния равен нулю, и он принимает отрицательные значения вне Ом. [1]Однако иногда вместо этого используется альтернативное соглашение (т. Е. Отрицательное внутри Ω и положительное снаружи). [2]
Определение
Если Ω является подмножеством из метрического пространства , X , с метрикой , д , то подписанное функции расстояния , F , определяются
где обозначает границу из. Для любой,
где inf обозначает нижнюю грань .
Свойства в евклидовом пространстве
Если Ω - подмножество евклидова пространства R n с кусочно гладкой границей, то функция расстояния со знаком дифференцируема почти всюду , а ее градиент удовлетворяет уравнению эйконала
Если граница Ω равна C k для k ≥ 2 (см. Классы дифференцируемости ), то d является C k в точках, достаточно близких к границе Ω. [3] В частности, на границе f удовлетворяет
где N - векторное поле внутренней нормали. Таким образом, функция расстояния со знаком является дифференцируемым расширением нормального векторного поля. В частности, гессиан функции расстояния со знаком на границе Ω дает отображение Вейнгартена .
Если, кроме того, Γ является областью, достаточно близкой к границе Ω, чтобы f дважды непрерывно дифференцируемо на ней, то существует явная формула, включающая отображение Вейнгартена W x для якобиана меняющихся переменных в терминах функции расстояния со знаком и ближайшая граничная точка. В частности, если T ( ∂ Ω, μ ) - это множество точек на расстоянии μ от границы Ω (т. Е. Трубчатая окрестность радиуса μ ), а g - абсолютно интегрируемая функция на Γ, то
где det обозначает определитель, а dS u указывает, что мы берем поверхностный интеграл . [4]
Алгоритмы
Алгоритмы для вычисления функции расстояния подписанного включают эффективный быстрый метод походного , быстрый метод радикального [5] и более общий метод уровня набора .
Приложения
Знаковые функции расстояния применяются, например, в рендеринге в реальном времени [6] и компьютерном зрении . [7] [8]
Была представлена модифицированная версия SDF для минимизации ошибки взаимопроникновения пикселей при рендеринге нескольких объектов. [9] В частности, для любого пикселя, который не принадлежит объекту, если он находится вне объекта при воспроизведении, штраф не налагается; если это так, накладывается положительное значение, пропорциональное его расстоянию внутри объекта.
Они также использовались в методе (продвинутом Valve ) для рендеринга гладких шрифтов большого размера (или, альтернативно, с высоким DPI ) с использованием ускорения графического процессора . [10] Метод Valve вычисляет поля расстояний со знаком в растровом пространстве , чтобы избежать вычислительной сложности решения задачи в (непрерывном) векторном пространстве. Совсем недавно были предложены решения для кусочной аппроксимации (которые, например, аппроксимируют кривую Безье с помощью дуговых сплайнов), но даже в этом случае вычисление может быть слишком медленным для рендеринга в реальном времени , и ему должны помогать методы дискретизации на основе сетки для аппроксимации (и исключения из вычислений) расстояния до точек, которые находятся слишком далеко. [11]
В 2020 году игровой движок FOSS Godot 4.0 получил глобальное освещение в реальном времени (SDFGI) на основе SDF, которое стало компромиссом между более реалистичным GI на основе вокселей и запеченным GI. Его основное преимущество заключается в том, что его можно применять к бесконечному пространству, что позволяет разработчикам использовать его для игр с открытым миром. [ необходима цитата ]
Смотрите также
- Функция расстояния
- Метод установки уровня
- Уравнение эйконала
- Параллельная (также известная как смещение) кривая
Заметки
- ^ Чан, Т .; Чжу, В. (2005). Предварительная сегментация формы на основе набора уровней . Конференция компьютерного общества IEEE по компьютерному зрению и распознаванию образов. DOI : 10,1109 / CVPR.2005.212 .
- ^ Malladi, R .; Sethian, JA; Вемури, Британская Колумбия (1995). «Моделирование формы с фронтальным распространением: подход с набором уровней». IEEE Transactions по анализу шаблонов и машинному анализу . 17 (2): 158–175. CiteSeerX 10.1.1.33.2443 . DOI : 10.1109 / 34.368173 .
- ^ Гилбарг 1983 , лемма 14.16.
- ^ Гилбарг 1983 , уравнение (14,98).
- ^ Чжао Хункай . Метод быстрого поиска для уравнений эйконала . Математика вычислений, 2005, 74. Jg., Nr. 250, С. 603-627.
- ^ Томас Акенин-Мёллер; Эрик Хейнс; Нати Хоффман (6 августа 2018 г.). Рендеринг в реальном времени, четвертое издание . CRC Press. ISBN 978-1-351-81615-1.
- ^ Perera, S .; Barnes, N .; Он, X .; Изади, С .; Коли, П .; Глокер, Б. (январь 2015 г.). "Сегментация движения объемных поверхностей на основе усеченной функции расстояния со знаком". Зимняя конференция IEEE 2015 г. по приложениям компьютерного зрения : 1046–1053. DOI : 10,1109 / WACV.2015.144 . ISBN 978-1-4799-6683-7. S2CID 16811314 .
- ^ Изади, Шахрам; Ким, Дэвид; Хиллигес, Отмар; Молино, Дэвид; Ньюкомб, Ричард; Коли, Пушмит; Шоттон, Джейми; Ходжес, Стив; Фриман, Дастин (2011). «KinectFusion: 3D-реконструкция и взаимодействие в реальном времени с помощью движущейся камеры определения глубины». Материалы 24-го ежегодного симпозиума ACM по программному обеспечению и технологиям пользовательского интерфейса . УИСТ '11. Нью-Йорк, Нью-Йорк, США: ACM: 559–568. DOI : 10.1145 / 2047196.2047270 . ISBN 9781450307161. S2CID 3345516 .
- ^ Цзян, Вэнь; Колотоурос, Никос; Павлакос, Георгиос; Чжоу, Сяовэй; Даниилидис, Костас (15.06.2020). «Последовательная реконструкция множества людей из одного изображения». arXiv : 2006.08586 [ cs.CV ].
- ^ Грин, Крис (2007). «Улучшено увеличение при альфа-тестировании векторных текстур и спецэффектов». ACM SIGGRAPH 2007 Курсы на - SIGGRAPH '07 : 9. CiteSeerX 10.1.1.170.9418 . DOI : 10.1145 / 1281500.1281665 . ISBN 9781450318235. S2CID 7479538 .
- ^ https://www.youtube.com/watch?v=7tHv6mcIIeo
Рекомендации
- Стэнли Дж. Ошер и Рональд П. Федкив (2003). Методы набора уровней и неявные динамические поверхности . Springer. ISBN 9780387227467.
- Gilbarg, D .; Трудингер, Н.С. (1983). Эллиптические дифференциальные уравнения с частными производными второго порядка . Grundlehren der Mathematischen Wissenschaften. 224 (2-е изд.). Springer-Verlag. (или Приложение 1-го изд. 1977 г.)