RBF jerárquico

En gráficos por computadora , la interpolación jerárquica RBF es un método de interpolación basado en funciones de base radial (RBF). La interpolación jerárquica RBF tiene aplicaciones en la construcción de modelos de formas en gráficos por computadora en 3D (ver la imagen del conejo de Stanford a continuación), el tratamiento de resultados de un escáner 3D , la reconstrucción de terrenos y otros.

Este problema se denomina informalmente "interpolación de grandes conjuntos de puntos de datos dispersos".

Los pasos del método (por ejemplo en 3D) consisten en lo siguiente:

• Dejemos que los puntos dispersos se presenten como un conjunto${\displaystyle \mathbf {P} =\{\mathbf {c} _{i}=(\mathbf {x} _{i},\mathbf {y} _{i},\mathbf {z} _{i})\vert _{i=1}^{N}\subset \mathbb {R} ^{3}\}}$
• Sea que exista un conjunto de valores de alguna función en puntos dispersos${\displaystyle \mathbf {H} =\{\mathbf {h} _{i}\vert _{i=1}^{N}\subconjunto \mathbb {R} \}}$
• Encuentre una función que cumpla la condición para los puntos que se encuentran en la forma y para los puntos que no se encuentran en la forma.${\displaystyle \mathbf {f} (\mathbf {x} )}$${\displaystyle \mathbf {f} (\mathbf {x} )=1}$${\displaystyle \mathbf {f} (\mathbf {x} )\neq 1}$
• Como lo demostraron JC Carr et al., ^[1] esta función se ve así:${\displaystyle \mathbf {f} (\mathbf {x} )=\sum _{i=1}^{N}\lambda _{i}\varphi (\mathbf {x} ,\mathbf {c} _{ i})}$

${\estilo de visualización \varphi}$— es RBF ; — son coeficientes que son la solución del sistema que se muestra en la imagen: ${\estilo de visualización \lambda}$

Para determinar la superficie, es necesario estimar el valor de la función en los puntos de interés x. La falta de dicho método supone una complicación considerable ^[2] para calcular RBF , resolver el sistema y determinar la superficie. ${\displaystyle \mathbf {f} (\mathbf {x} )}$ ${\displaystyle \mathbf {O} (\mathbf {n} ^{2})}$

• Reducir los centros de interpolación ( para calcular RBF y resolver el sistema , para determinar la superficie)${\displaystyle \mathbf {O} (\mathbf {n} ^{2})}$${\displaystyle \mathbf {O} (\mathbf {m} \mathbf {n} )}$
• Admite de forma compacta RBF ( para calcular RBF , para resolver el sistema , para determinar la superficie)${\displaystyle \mathbf {O} (\mathbf {n} \log {\mathbf {n} })}$${\displaystyle \mathbf {O} (\mathbf {n} ^{1.2..1.5})}$${\displaystyle \mathbf {O} (\mathbf {m} \log {\mathbf {n} })}$
• FMM ( para calcular RBF , para resolver el sistema , para determinar la superficie)${\displaystyle \mathbf {O} (\mathbf {n} ^{2})}$${\displaystyle \mathbf {O} (\mathbf {n} \log {\mathbf {n} })}$${\displaystyle \mathbf {O} (\mathbf {m} +\mathbf {n} \log {\mathbf {n} })}$

Una idea del algoritmo jerárquico es una aceleración de los cálculos debido a la descomposición de problemas complejos en un gran número de problemas simples (ver imagen).

En este caso, la división jerárquica del espacio contiene puntos en partes elementales, y el sistema de pequeña dimensión resuelve cada una. El cálculo de la superficie en este caso se lleva al cálculo jerárquico (sobre la base de la estructura de árbol ) del interpolador. Pouderoux J. et al. ^[3] ofrece un método para un caso 2D . Para un caso 3D , se utiliza un método en las tareas de gráficos 3D de W. Qiang et al. ^[4] y modificado por Babkov V. ^[5].