Función de distancia con signo

Distancia de un punto al límite de un conjunto

La gráfica (abajo, en rojo) de la distancia con signo entre los puntos del plano xy (en azul) y un disco fijo (también representado arriba, en gris)

Un conjunto más complicado (arriba) y el gráfico de su función de distancia con signo (abajo, en rojo).

En matemáticas y sus aplicaciones, la función de distancia con signo o campo de distancia con signo ( SDF ) es la distancia ortogonal de un punto dado x al límite de un conjunto Ω en un espacio métrico (como la superficie de una forma geométrica), con el signo determinado por si x está o no en el interior de Ω. La función tiene valores positivos en los puntos x dentro de Ω, disminuye en valor a medida que x se acerca al límite de Ω donde la función de distancia con signo es cero, y toma valores negativos fuera de Ω. ^[1] Sin embargo, a veces también se toma la convención alternativa (es decir, negativo dentro de Ω y positivo fuera). ^[2] El concepto también se conoce a veces con el nombre de función/campo de distancia orientado .

Definición

Sea Ω un subconjunto de un espacio métrico X con métrica d , y sea su frontera . La distancia entre un punto x de X y el subconjunto de X se define como de costumbre como ${\displaystyle \partial \Omega }$ ${\displaystyle \partial \Omega }$

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

donde denota el ínfimo . ${\displaystyle \inf }$

La función de distancia con signo desde un punto x de X hasta está definida por ${\displaystyle \Omega }$

${\displaystyle f(x)={\begin{cases}d(x,\partial \Omega )&{\text{if }}x\in \Omega \\-d(x,\partial \Omega )&{\text{if }}\,x\notin \Omega .\end{cases}}}$

Propiedades en el espacio euclidiano

Si Ω es un subconjunto del espacio euclidiano R ⁿ con un límite suave por partes , entonces la función de distancia con signo es diferenciable casi en todas partes , y su gradiente satisface la ecuación eikonal

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

Si el límite de Ω es C ^k para k ≥ 2 (ver Clases de diferenciabilidad ) entonces d es C ^k en puntos suficientemente cercanos al límite de Ω. ^[3] En particular, en el límite f satisface

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

donde N es el campo vectorial normal interno . La función de distancia con signo es, por lo tanto, una extensión diferenciable del campo vectorial normal. En particular, la hessiana de la función de distancia con signo en el límite de Ω da la función de Weingarten .

Si, además, Γ es una región suficientemente cercana al límite de Ω como para que f sea dos veces continuamente diferenciable en ella, entonces existe una fórmula explícita que involucra la función de Weingarten W _x para el jacobiano de variables cambiantes en términos de la función de distancia con signo y el punto límite más cercano. Específicamente, si T ( ∂ Ω, μ ) es el conjunto de puntos dentro de la distancia μ del límite de Ω (es decir, el vecindario tubular de radio μ ), y g es una función absolutamente integrable en Γ, entonces

${\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},}$

donde det denota el determinante y dS _u indica que estamos tomando la integral de superficie . ^[4]

Algoritmos

Los algoritmos para calcular la función de distancia con signo incluyen el método de marcha rápida eficiente , el método de barrido rápido ^[5] y el método de nivel establecido más general .

Para la representación de vóxeles , un algoritmo rápido para calcular la SDF en la geometría del taxi utiliza tablas de áreas sumadas . ^[6]

Aplicaciones

Los campos de distancia firmados almacenados como imágenes raster se pueden utilizar para representar formas.

Las funciones de distancia con signo se aplican, por ejemplo, en la representación en tiempo real , ^[7] por ejemplo el método de marcha de rayos SDF y la visión por computadora . ^{[8] [9]}

SDF se ha utilizado para describir la geometría de objetos en renderizado en tiempo real , generalmente en un contexto de raymarching, a partir de mediados de la década de 2000. En 2007, Valve está utilizando SDF para renderizar fuentes suaves de gran tamaño de píxel (o alto DPI ) con aceleración de GPU en sus juegos. ^[10] El método de Valve no es perfecto, ya que se ejecuta en el espacio raster para evitar la complejidad computacional de resolver el problema en el espacio vectorial (continuo). El texto renderizado a menudo pierde esquinas agudas. En 2014, Behdad Esfahbod presentó un método mejorado . GLyphy de Behdad aproxima las curvas de Bézier de la fuente con splines de arco, aceleradas por técnicas de discretización basadas en cuadrícula (que descartan puntos demasiado lejanos) para ejecutarse en tiempo real. ^[11]

Se introdujo una versión modificada de SDF como una función de pérdida para minimizar el error en la interpenetración de píxeles al renderizar múltiples objetos. ^[12] En particular, para cualquier píxel que no pertenece a un objeto, si se encuentra fuera del objeto en la renderización, no se impone ninguna penalización; si lo hace, se impone un valor positivo proporcional a su distancia dentro del objeto.

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

En 2020, el motor de juegos FOSS Godot 4.0 recibió iluminación global en tiempo real basada en SDF (SDFGI), que se convirtió en un compromiso entre la GI basada en vóxeles más realista y la GI horneada. Su principal ventaja es que se puede aplicar al espacio infinito, lo que permite a los desarrolladores usarlo para juegos de mundo abierto. ^[13]

En 2023, se lanzó un marco de interfaz de usuario "GPUI" para dibujar todos los elementos de la interfaz de usuario utilizando la GPU, muchas partes utilizando SDF. El autor afirma haber producido un editor de código Zed que se renderiza a 120 fps. El trabajo hace uso de la lista de primitivas geométricas de Inigo Quilez en SDF, el desenfoque gaussiano aproximado de Evan Wallace (cofundador de Figma ) en SDF y un nuevo SDF de rectángulo redondeado. ^[14]

Véase también

• Función de distancia
• Método de nivelación
• Ecuación eikonal
• Curva paralela (también conocida como curva desplazada)
• Longitud de arco con signo
• Área firmada
• Medida firmada
• Volumen firmado

Notas

1. Chan, T.; Zhu, W. (2005). Segmentación previa de forma basada en conjuntos de niveles . Conferencia de la IEEE Computer Society sobre visión artificial y reconocimiento de patrones. doi :10.1109/CVPR.2005.212.
2. Malladi, R.; Sethian, JA; Vemuri, BC (1995). "Modelado de formas con propagación frontal: un enfoque de conjunto de niveles". IEEE Transactions on Pattern Analysis and Machine Intelligence . 17 (2): 158–175. CiteSeerX 10.1.1.33.2443 . doi :10.1109/34.368173. S2CID  9505101. 
3. Gilbarg y Trudinger 1983, Lema 14.16.
4. Gilbarg y Trudinger 1983, Ecuación (14.98).
5. Zhao Hongkai . Un método de barrido rápido para ecuaciones eikonales. Matemáticas de la computación, 2005, 74. Jg., Nr. 250, págs. 603-627.
6. Nilsson, Tobías (2019). "Métodos de optimización para la representación directa de volúmenes en la web del lado del cliente" (PDF) . Digital Vetenskapliga Arkivet . Consultado el 8 de julio de 2022 .
7. Tomas Akenine-Möller; Eric Haines; Naty Hoffman (6 de agosto de 2018). Real-Time Rendering, cuarta edición. CRC Press. ISBN 978-1-351-81615-1.
8. Perera, S.; Barnes, N.; He, X.; Izadi, S.; Kohli, P.; Glocker, B. (enero de 2015). "Segmentación de movimiento de superficies volumétricas basadas en funciones de distancia con signo truncadas". Conferencia de invierno IEEE de 2015 sobre aplicaciones de visión artificial . págs. 1046–1053. doi :10.1109/WACV.2015.144. ISBN 978-1-4799-6683-7. Número de identificación del sujeto  16811314.
9. Izadi, Shahram; Kim, David; Hilliges, Otmar; Molyneaux, David; Newcombe, Richard; Kohli, Pushmeet; Shotton, Jamie; Hodges, Steve; Freeman, Dustin (2011). "KinectFusion". Actas del 24.º simposio anual de la ACM sobre software y tecnología de interfaz de usuario . UIST '11. Nueva York, NY, EE. UU.: ACM. págs. 559–568. doi :10.1145/2047196.2047270. ISBN . 9781450307161.S2CID3345516  .​
10. Green, Chris (2007). "Aumento mejorado con pruebas alfa para texturas vectoriales y efectos especiales". Cursos ACM SIGGRAPH 2007. Págs. 9-18. CiteSeerX 10.1.1.170.9418 . Doi : 10.1145/1281500.1281665. ISBN .  9781450318235.S2CID 7479538  .
11. Behdad Esfahbod. GLyphy: renderizado de glifos de alta calidad con sombreadores OpenGL ES2 [linux.conf.au 2014]. YouTube . Archivado desde el original el 11 de diciembre de 2021.Código fuente
12. Jiang, Wen; Kolotouros, Nikos; Pavlakos, Georgios; Zhou, Xiaowei; Daniilidis, Kostas (15 de junio de 2020). "Reconstrucción coherente de múltiples seres humanos a partir de una única imagen". arXiv : 2006.08586 [cs.CV].
13. Motor Godot. "Godot 4.0 obtiene iluminación global en tiempo real basada en SDF". Motor Godot .
14. Scandurra, Antonio (7 de marzo de 2023). "Aprovechamiento de Rust y la GPU para renderizar interfaces de usuario a 120 FPS - Blog de Zed". Zed .

Referencias

• Stanley J. Osher y Ronald P. Fedkiw (2003). Métodos de conjunto de niveles y superficies implícitas dinámicas. Springer. ISBN 9780387227467.
• Gilbarg, D.; Trudinger, NS (1983). Ecuaciones diferenciales parciales elípticas de segundo orden . Grundlehren der mathematischen Wissenschaften. vol. 224 (2ª ed.). Springer-Verlag.(o el Apéndice de la 1ª ed. de 1977.)