Forma sencilla de interpolar puntos en el espacio tridimensional para formar una superficie lisa

Question

Estoy tratando de encontrar una forma simple y eficiente de crear una superficie lisa que intersecte una cantidad determinada de puntos de "muestra".

Para cualquier punto X, Y en la superficie, identifico hasta 4 puntos de muestra en cada una de las 4 direcciones (el siguiente punto más alto y más bajo en la X, y luego los ejes Y). Dado este punto, quiero una forma de calcular un valor Z que interpola entre los 4 puntos de muestra.

Por supuesto, el algoritmo, dada la posición X, Y de cualquiera de los 4 puntos de muestra, debe generar el valor Z para ese punto. Tenga en cuenta también que puede haber menos de 4 puntos de muestra.

Supongo que alguna función de los valores Z para los 4 puntos de muestra, de alguna manera inversamente sesgada por la distancia al punto de muestra, pero no puedo encontrar la manera de hacerlo.

¿Alguien tiene alguna idea sobre una manera simple de hacer esto?

Answer 1

Puede hacerlo mediante la construcción de parches desde las splines de Catmull-Rom. Estas splines afectarán a cada uno de los puntos de control y son continuas en la primera derivada (aunque no en la segunda). También me parece que es extremadamente fácil trabajar con ellos. La matemática es directa y se comportan intuitivamente con ligeros cambios en los puntos de control.

En el nivel más alto, necesitará 16 puntos por parche (en el borde de su conjunto de datos, puede usar los puntos de esquina y borde dos veces en la misma spline).

En primer lugar, tendrá que interpolar entre los puntos de p [i] [j] en cada fila de la matriz de 4x4 para crear un conjunto de cuatro puntos de control intermedios q [i]. Aquí hay un bosquejo ASCII aproximado de lo que quiero decir.

p00 p01 q0 p02 p03 
p10 p11 q1 p12 p13 
p20 p21 q2 p22 p23 
p30 p31 q3 p32 p33 

Ahora se puede interpolar entre cada uno de los cuatro puntos de control intermedios para encontrar un punto acanalado final sobre su superficie.

Here is a construction of the Catmull-Rom spline en cuatro puntos. En este ejemplo, que está interpolando entre los puntos p [i-1] y p [i], utilizando puntos de control en cualquiera de p lado [i-2] y p [i + 1]. u es el factor de interpolación que va de cero a uno. τ se define como la tensión en la spline y afectará la fuerza con la que su superficie estriada se ajusta a sus puntos de control.

    | 0 1 0 0 | | p[i−2] | 
       |−τ 0 τ 0 | | p[i−1] | 
p(u) = 1 u u2 u3 | 2τ τ−3 3−2τ −τ | | p[i] | 
       |−τ 2−τ τ−2 τ | | p[i+1] | 

NOTA: no es inmediatamente obvio cómo poner esto en la GUI de Stackoverflow pero U2 y U3 se supone que representa u cuadrados y u al cubo, respectivamente.

Answer 2

utilizará los parches Catmull-ROM

Answer 3

Se pueden utilizar bilineal/interpolación bicúbica, pero en tres direcciones (trilineal/tricubic, respectivamente). Es bastante trivial si comprendes cómo funcionan estas formas de interpolación. Consulte Tricubic Interpolation on Wikipedia para obtener más información.

Answer 4

Si desea una interpolación lineal simple de ese punto, entonces el valor Z del punto central es más que la media de los 4 valores Z vecinos, dadas las distancias son simétricas en ambos Y y X.

Si las distancias no son simétricas, pero el punto central siempre está en las mismas líneas X e Y, puede calcular las interpolaciones Y y X, y el valor final es la media de esas.

Así Zc sería: Zc = (Zx1 + x * (Zx2-Zx1)/(x2-x1) + Zy1 + y * (Zy2-Zy1)/(y2-y1))/2, donde xy y son distancias de x1 y y1.

Answer 5

¿Está buscando una interpolación de superficie o una grilla sería suficiente?

Para una interpolación superficie veo que otros han sugerido el uso de triangulaciones (por ejemplo utilizar este: http://en.wikipedia.org/wiki/Delaunay_triangulation)

Para la creación de una cuadrícula: uno de mis colegas utilizaron la ecuación del calor (http://en.wikipedia.org/wiki/Heat_equation) para calcular los valores de píxeles fuera de los puntos de muestra dados. Esto produjo superficies de terreno de aspecto extremadamente realista, y fue trivial para paralelizar.

Answer 6

Un problema al interpolar utilizando el esquema sugerido en la pregunta, en el que algún subconjunto de vecinos más cercanos se eligen de un conjunto disperso, es que el resultado no necesita ser continuo.

Piénselo. Supongamos que debo moverme a lo largo de un camino suave y continuo a través del plano (x, y). Siempre y cuando los 4 vecinos más cercanos no cambien, el interpolador será suave, definido como lo prefiera. Sin embargo, en algún momento, ese subconjunto de vecinos más cercanos cambiará repentinamente. En ese punto, debe tener el interpolador constante a través del límite. Lo mejor es usar una triangulación del conjunto de variables independientes. Esto asegura un interpolador continuo (lineal) dentro del casco convexo de los datos. Con más trabajo, también se pueden lograr interpolaciones de orden superior con una triangulación.

Las funciones de base radial también se suelen utilizar también para la interpolación, o Kriging, si le interesa la geoestadística. Como estaba buscando métodos basados ​​en distancia, considere las funciones de base radial. Por ejemplo, busque "interpolación multiquárica inversa".