Signed distance function

Original article: w:Signed distance function

The graph (bottom, in red) of the signed distance between a fixed disk (top, in grey) and a point of the plane containing the disk (the xy plane, shown in blue)

A more complicated set (top) and the graph of its signed distance function (bottom, in red).

수학(mathematics)과 해당 응용에서, 부호화된 거리 함수 (또는 방향화된 거리 함수)는 메트릭 공간(metric space)에서 주어진 점 x와 집합 Ω의 경계(boundary)까지의 직교 거리(orthogonal distance)이며, 그 부호는 x가 Ω의 내부(interior)에 있는지 여부에 따라 결정됩니다. 그 함수(function)는 Ω 내부의 점 x에서 양수 값을 가지며, x가 부호화된 거리 함수가 0인 Ω의 경계에 접근함에 따라 값이 감소하고, Ω의 외부에서 음수 값을 취합니다. 어쨌든, 대안적인 규칙이 대신 취해지기도 합니다 (즉, Ω 내부는 음수를 취하고 외부는 양수를 취합니다).

Definition

만약 Ω가 메트릭(metric) d를 갖는 메트릭 공간(metric space) X의 부분집합(subset)이면, 부호화된 거리 함수 f는 다음에 의해 정의됩니다:

$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}}$

여기서 $\partial \Omega$는 $\Omega$의 경계(boundary)를 나타냅니다. 임의의 $x\in X$에 대해,

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

여기서 inf는 하한(infimum)을 나타냅니다.

Properties in Euclidean space

만약 Ω가 조각별(piecewise) 매끄러운(smooth) 경계를 갖는 유클리드 공간(Euclidean space) Rⁿ의 부분공간이면, 부호화된 거리 함수는 거의 모든 곳에서(almost everywhere) 미분가능이고, 그것의 그래디언트(gradient)는 에이코날 방정식(eikonal equation)을 만족시킵니다:

$|\nabla f|=1.$

만약 Ω의 경계가 k ≥ 2에 대해 C^k이면 (미분가능 클래스(Differentiability classes) 참조), d는 Ω의 경계에 충분하게 가까운 점 위의 C^k입니다. 특히, 경계 위의 f는 다음을 만족시킵니다:

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

여기서 N은 내부를 향하는 법선 벡터 필드입니다. 부호화된 거리 함수는 따라서 법선 벡터 필드의 미분-가능 확장입니다. 특히, Ω의 경계 위의 부호화된 거리 함수의 헤세(Hessian)는 바인가르튼 맵(Weingarten map)을 제공합니다.

더 나아가서, 만약 Γ가 Ω의 경계에 충분하게 가까운 영역으로 f가 그것 위에 두 번 연속적으로 미분-가능이면, 부호화된 거리 함수와 가장 가까운 경계 점의 관점에서 변수를 변경하는 야코비 행렬에 대한 바인가르튼 맵 W_x를 포함하는 명시적 공식이 있습니다. 구체적으로 특별히, 만약 T(∂Ω, μ)가 Ω 경계의 거리 μ 내에 있는 점 집합 (즉, 반지름 μ의 관형 이웃(tubular neighbourhood))이고, g가 Γ 위에 절대적으로 적분-가능 함수(absolutely integrable function)이면,$$\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는 행렬식(determinant)을 나타내고 dS_u는 우리가 표면 적분(surface integral)을 취하는 것을 표시합니다.

Algorithms

부호화된 거리 함수를 계산하는 알고리듬(algorithms)은 효율적인 빠른 행진 방법(fast marching method), 빠른 청소 방법(fast sweeping method), 및 보다 일반적인 수준-집합 방법(level-set method)을 포함합니다.

복셀(voxel) 렌더링에 대해, 택시 기하학(taxicab geometry)에서 SDF를 계산하는 빠른 알고리듬은 합산-넓이 테이블(summed-area tables)을 사용합니다.

Applications

Signed distance fields stored as raster images can be used to represent shapes.

부호화된 거리 함수는 예를 들어 실시간 렌더링(real-time rendering), 예를 들어 SDF 반직선 행진(SDF ray marching)과 컴퓨터 비전(computer vision)에 적용됩니다.

SDF의 수정된 버전은 여러 대상을 렌더링하는 동안 픽셀의 상호-침투에서 오류를 최소화하기 위해 손실 함수(loss function)로 도입되었습니다. 특히, 대상에 속하지 않는 임의의 픽셀에 대해, 만약 그것이 변환에서 대상 외부에 놓이면, 페널티가 부과되지 않습니다; 만약 그렇다면 대상 내부의 그것의 거리에 비례하는 양의 값이 부과됩니다.

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

그것들은 역시 GPU 가속을 사용하여 큰 크기 (또는 대안적으로 높은 DPI에서) 매끄러운 글꼴(smooth fonts)을 렌더링하는 방법 (Valve에 의해 발전됨)에 사용되어 왔습니다. 밸브의 방법은 (연속) 벡터 공간에서 문제를 해결하는 계산의 복잡성을 피하기 위해 래스터 공간(raster space)에서 부호화된 거리 필드(distance fields)를 계산했습니다. 더 최근에 조각별 근사화 해결책이 제안되어 왔지만 (예를 들어 호 스플라인을 갖는 베지어를 근사화함), 이 방법으로도 실시간 렌더링(real-time rendering)에는 계산이 너무 느려질 수 있고, 너무 멀리 있는 점까지의 거리를 근사화 (및 계산에서 추출)하기 위해 그리드-기반 이산화(discretization) 기술의 지원을 받아야 합니다.

2020년에, FOSS 게임 엔진 Godot 4.0은 SDF 기반의 실-시간 전역 조명(global illumination) (SDFGI)을 받아 보다 사실적인 복셀 기반 GI와 구운 GI 사이의 절충안이 되었습니다. 그것의 핵심 장점은 무한 공간에 적용할 수 있어 개발자가 오픈 월드 게임에 사용할 수 있다는 것입니다.

See also

• Distance function
• Level-set method
• Eikonal equation
• Parallel (aka offset) curve
• Signed arc length

References

• 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. Vol. 224 (2nd ed.). Springer-Verlag. (or the Appendix of the 1977 1st ed.)