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

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

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

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

Определение

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

{\ Displaystyle е (х) = {\ begin {case} d (x, \ partial \ Omega) & {\ mbox {if}} \, x \ in \ Omega \\ - d (x, \ partial \ Omega) & {\ mbox {if}} \, x \ in \ Omega ^ {c} \ end {case}}}

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

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

где $inf$ обозначает нижнюю грань .

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

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

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

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

{\ Displaystyle \ набла е (х) = N (х),}

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

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

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

Алгоритмы

Алгоритмы для вычисления функции расстояния подписанного включают эффективный быстрый метод походного , быстрый метод радикальный и более общий метод уровня набора .

Приложения

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

Знаковые функции расстояния применяются, например, при визуализации в реальном времени и компьютерном зрении .

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

${\ displaystyle f (x) = {\ begin {case} 0 & {\ text {if}} \, x \ in \ Omega ^ {c} \\ d (x, \ partial \ Omega) & {\ text {если }} \, x \ in \ Omega \ end {case}}}$

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

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

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

Примечания

использованная литература

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

Languages

In other projects