Podepsaná funkce vzdálenosti - Signed distance function

Disk (nahoře, šedě) a funkce vzdálenosti se znaménkem (dole, červeně). The X-y letadlo je zobrazeno modře.

Složitější sada (nahoře) a její funkce vzdálenosti se znaménkem (dole, červeně).

v matematika a jeho aplikace, podepsaná funkce vzdálenosti (nebo funkce orientované vzdálenosti) sady Ω v metrický prostor určuje vzdálenost daného bodu X z hranice z Ω, se znamením určeným podle toho, zda X je v Ω. Funkce má kladné hodnoty v bodech X uvnitř Ω, klesá hodnota jako X se blíží hranici Ω kde funkce vzdálenosti se znaménkem je nula a mimo ni bere záporné hodnoty Ω.^[1] Alternativní konvence je však také někdy brána místo (tj. Negativní uvnitř Ω a pozitivní venku).^[2]

Definice

Li Ω je podmnožinou a metrický prostor, X, s metrickými, d, pak podepsaná funkce vzdálenosti, F, je definováno

${ displaystyle f (x) = { začátek {případů} d (x, částečný Omega) & { mbox {if}} x v Omega - d (x, částečný Omega) & { mbox {if}} x in Omega ^ {c} end {případy}}}$

kde ${ displaystyle částečné Omega}$ označuje hranice z ${ displaystyle Omega}$. Pro všechny ${ displaystyle x v X}$,

${ displaystyle d (x, částečné Omega): = inf _ {y v částečné Omega} d (x, y)}$

kde inf označuje infimum.

Vlastnosti v euklidovském prostoru

Li Ω je podmnožinou souboru Euklidovský prostor Rⁿ s po částech hladký hranice, pak je funkce vzdálenosti se znaménkem diferencovatelná téměř všude, a jeho spád uspokojuje eikonální rovnice

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

Pokud je hranice Ω je C^k pro k≥2 (viz třídy diferencovatelnosti ) pak d je C^k v bodech dostatečně blízko k hranici Ω.^[3] Zejména, na hranice F splňuje

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

kde N je vnitřní normální vektorové pole. Funkce vzdálenosti se znaménkem je tedy diferencovatelné rozšíření normálního vektorového pole. Zejména Hesián funkce vzdálenosti se znaménkem na hranici Ω dává Mapa Weingarten.

Pokud dále Γ je oblast dostatečně blízko k hranici Ω že F je na něm dvakrát průběžně diferencovatelné, pak existuje explicitní vzorec zahrnující mapu Weingarten Ž_X pro Jacobiana měnících se proměnných, pokud jde o funkci vzdálenosti se znaménkem a nejbližší hraniční bod. Konkrétně pokud T(∂Ω,μ) je množina bodů ve vzdálenosti μ hranice Ω (tj trubkové sousedství poloměru μ), a G je naprosto integrovatelná funkce na Γ, pak

${ displaystyle int _ {T ( částečné Omega, mu)} g (x) , dx = int _ { částečné Omega} int _ {- mu} ^ { mu} g ( u + lambda N (u)) , det (I- lambda W_ {u}) , d lambda , dS_ {u},}$

kde det označuje určující a dS_u naznačuje, že užíváme povrchový integrál.^[4]

Algoritmy

Algoritmy pro výpočet funkce podepsané vzdálenosti zahrnují efektivní metoda rychlého pochodu, metoda rychlého zametání^[5] a obecnější metoda nastavení úrovně.

Aplikace

Podepsaná pole vzdálenosti uložená jako rastrové obrázky lze použít k reprezentaci tvarů.

Podepsané funkce vzdálenosti se používají například v vykreslování v reálném čase^[6] a počítačové vidění.^[7][8]

Byly také použity v metodě (rozšířené o Ventil ) k vykreslení hladká písma ve velkých velikostech (nebo alternativně v vysoké DPI ) použitím GPU akcelerace.^[9] Vypočtená metoda ventilu podepsaná pole vzdálenosti v rastrový prostor aby se zabránilo výpočetní složitosti řešení problému v (spojitém) vektorovém prostoru. V poslední době byla navržena kusová aproximační řešení (která například aproximují Béziera s obloukovými spline), ale i tak může být výpočet příliš pomalý vykreslování v reálném čase, a musí mu být nápomocen gridový systém diskretizace techniky k aproximaci (a vyřazení z výpočtu) vzdálenosti k bodům, které jsou příliš daleko.^[10]

V roce 2020 FOSS herní engine Godot 4.0 obdržel v reálném čase založené na SDF globální osvětlení (SDFGI), který se stal kompromisem mezi realističtějším GI na bázi voxelů a zapečeným GI. Jeho hlavní výhodou je, že jej lze použít v nekonečném prostoru, což vývojářům umožňuje používat jej pro hry v otevřeném světě.^{[Citace je zapotřebí ]}

Viz také

• Funkce vzdálenosti
• Metoda nastavení úrovně
• Eikonální rovnice
• Paralelní (aka offsetová) křivka

Poznámky

Reference

• Stanley J. Osher a Ronald P. Fedkiw (2003). Metody nastavení úrovní a dynamické implicitní povrchy. Springer. ISBN  9780387227467.
• Gilbarg, D .; Trudinger, N. S. (1983). Eliptické parciální diferenciální rovnice druhého řádu. Grundlehren der mathematischen Wissenschaften. 224 (2. vyd.). Springer-Verlag. (nebo dodatek z 1. vydání z roku 1977)