Signerad distansfunktion

Grafen (botten, i rött) över det tecken som avståndet mellan en fast skiva ( överst, i grått) och en punkt på planet som innehåller skivan (xy- planet , visat i blått)

En mer komplicerad uppsättning (överst) och grafen för dess signerade avståndsfunktion (nederst, i rött).

I matematik och dess tillämpningar är teckenavståndsfunktionen (eller orienterad avståndsfunktion ) det ortogonala avståndet för en given punkt x till gränsen för en uppsättning Ω i ett metriskt utrymme , med tecknet bestämt av om x är i det inre eller inte av Ω. Funktionen har positiva värden vid punkter x inuti Ω, den minskar i värde när x närmar sig gränsen för Ω där avståndsfunktionen med tecken är noll, och den tar negativa värden utanför Ω . Men den alternativa konventionen tas också ibland istället (dvs. negativ inuti Ω och positiv utanför).

Definition

Om Ω är en delmängd av ett metriskt utrymme X med metriskt d , så definieras den förtecknade avståndsfunktionen f av

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

där $\partial \Omega$ anger gränsen för $\Omega$ . För alla $x\in X$ ,

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

där $inf$ betecknar infimum .

Egenskaper i det euklidiska rummet

Om Ω är en delmängd av det euklidiska utrymmet R ⁿ med en bitvis jämn gräns, så är funktionen för teckenavstånd differentierbar nästan överallt , och dess gradient uppfyller den ekonala ekvationen

|\nabla f|=1.

Om gränsen för Ω är C ^k för k ≥ 2 (se Differentieringsklasser ) så är d C ^k på punkter tillräckligt nära gränsen för Ω. I synnerhet på gränsen f uppfyller

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

där N är det inåtriktade normalvektorfältet. Funktionen för teckenavstånd är således en differentierbar förlängning av det normala vektorfältet. Speciellt hessian för teckenavståndsfunktionen på gränsen för Ω Weingarten-kartan .

Om vidare Γ är en region som är tillräckligt nära gränsen för Ω att f är två gånger kontinuerligt differentierbar på den, så finns det en explicit formel som involverar Weingarten-kartan W _x för Jacobian för att ändra variabler i termer av teckenavståndsfunktionen och närmaste gränspunkt. Specifikt, om T ( ∂ Ω, μ ) är uppsättningen punkter inom avståndet μ från gränsen för Ω (dvs. det rörformiga området med radien μ ), och g är en absolut integrerbar funktion på Γ, då

{\displaystyle

där $det$ betecknar determinanten och dS _u indikerar att vi tar ytintegralen .

Algoritmer

Algoritmer för att beräkna funktionen för teckenavstånd inkluderar den effektiva snabbmarschmetoden , snabbsvepmetoden och den mer allmänna nivåuppsättningsmetoden .

För voxelrendering använder en snabb algoritm för beräkning av SDF i taxibilsgeometri summerade areatabeller .

Ansökningar

Signerade avståndsfält lagrade som rasterbilder kan användas för att representera former.

Signerade avståndsfunktioner tillämpas till exempel i realtidsrendering , till exempel metoden för SDF-strålmarsch och datorseende .

SDF har använts för att beskriva objektgeometri i realtidsrendering, vanligtvis i ett raymarching-sammanhang, med början i mitten av 2000-talet. År 2007 Valve SDF:er för att göra jämna teckensnitt med stor pixelstorlek (eller hög DPI ) med GPU- acceleration i sina spel. Valves metod är inte perfekt då den körs i rasterrymden för att undvika beräkningskomplexiteten med att lösa problemet i det (kontinuerliga) vektorrummet. Den renderade texten tappar ofta skarpa hörn. 2014 presenterades en förbättrad metod av Behdad Esfahbod . Behdads GLyphy approximerar teckensnittets Bézier-kurvor med bågsplines, accelererade av rutnätsbaserade diskretiseringstekniker (som tar bort punkter för långt bort) för att köras i realtid.

En modifierad version av SDF introducerades som en förlustfunktion för att minimera felet i interpenetration av pixlar samtidigt som flera objekt renderas. I synnerhet, för varje pixel som inte tillhör ett objekt, om den ligger utanför objektet i återgivningen, utdöms inget straff; om den gör det, tilldelas ett positivt värde proportionellt mot dess avstånd inuti objektet.

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

2020 fick FOSS- spelmotorn Godot 4.0 SDF-baserad global belysning i realtid (SDFGI), som blev en kompromiss mellan mer realistiskt voxel-baserad GI och bakad GI. Dess centrala fördel är att den kan appliceras på oändligt utrymme, vilket gör att utvecklare kan använda den för spel i öppen värld.

2023 släpptes ett "GPUI" UI-ramverk för att rita alla UI-element med GPU:n, många delar med SDF. Författaren påstår sig ha producerat en Zed -kodredigerare som renderar med 120 fps. Verket använder sig av Inigo Quilez' lista över geometriska primitiver i SDF, Evan Wallace (medgrundare av Figma )'s approximerade gaussiska oskärpa i SDF och en ny rundad rektangel SDF.

Se även

Anteckningar

Stanley J. Osher och Ronald P. Fedkiw (2003). Nivåuppsättningsmetoder och dynamiska implicita ytor . Springer. ISBN 9780387227467 .
Gilbarg, D.; Trudinger, NS (1983). Elliptiska partiella differentialekvationer av andra ordningen . Grundlehren der mathematischen Wissenschaften. Vol. 224 (andra upplagan). Springer-Verlag. (eller bilagan till 1977 års första upplaga)