Einfache Möglichkeit, zwischen Punkten im 3D-Raum zu interpolieren, um eine glatte Oberfläche zu erhalten

Question

Ich versuche, eine einfache und effiziente Methode zu finden, um eine glatte Oberfläche zu erzeugen, die eine Anzahl vorgegebener "Sample" -Punkte schneidet.

Für jeden X, Y-Punkt auf der Oberfläche identifiziere ich bis zu 4 Abtastpunkte in jeder der 4 Richtungen (die nächsthöheren und tieferen Punkte auf dem X und dann die Y-Achsen). Mit diesem Punkt möchte ich einen Weg finden, einen Z-Wert zu berechnen, der zwischen den 4 Abtastpunkten interpoliert.

Natürlich sollte der Algorithmus, gegeben die X, Y-Position eines der 4 Beispielpunkte, den Z-Wert für diesen Punkt ausgeben. Beachten Sie auch, dass weniger als 4 Beispielpunkte vorhanden sein können.

Ich denke, eine Funktion der Z-Werte für die 4 Sample-Punkte, irgendwie umgekehrt durch die Entfernung zum Sample-Punkt vorgespannt, aber ich kann nicht herausfinden, wie dies zu tun ist.

Wer hat irgendwelche Ideen über eine einfache Möglichkeit, dies zu tun?

Answer 1

Sie können dies tun, indem Sie Patches aus Catmull-Rom-Splines erstellen. Diese Splines treffen jeden der Kontrollpunkte, und sie sind in der ersten Ableitung stetig (aber nicht in der zweiten). Ich finde auch, dass sie sehr einfach zu handhaben sind. Die Mathematik ist einfach und sie verhalten sich intuitiv mit leichten Änderungen der Kontrollpunkte.

Auf der höchsten Ebene benötigen Sie 16 Punkte pro Patch (am Rand Ihres Datasets können Sie die Eck- und Kantenpunkte zweimal im selben Spline verwenden).

Zuerst müssen Sie über die Punkte p [i] [j] in jeder Zeile in der 4x4-Matrix erstellen einen Satz von vier Zwischenkontrollpunkt q [i] zu interpolieren. Hier ist eine grobe ASCII-Skizze dessen, was ich meine.

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

Jetzt können Sie zwischen jedem dieser vier Zwischenkontrollpunkte interpolieren, um einen endgültigen Punkt auf Ihrer Oberfläche zu finden.

Here is a construction of the Catmull-Rom spline über vier Punkte. In diesem Beispiel sind sie zwischen den Punkten P [i-1] undp [i] Interpolation unter Verwendung von Kontrollpunkten auf beiden Seiten P [i-2] undp [i + 1]. u ist der Interpolationsfaktor von Null bis Eins. τ ist definiert als die Spannung auf dem Spline und beeinflusst, wie fest Ihre spline Oberfläche mit Ihren Kontrollpunkten übereinstimmt.

    | 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] | 

Hinweis: es ist nicht sofort klar, wie dies in der Stackoverflow gui legen, aber u2 und u3 sollen darstellen u squared und u Würfel geschnitten sind.

Answer 2

Verwenden Catmull-Rom-Patches

Answer 3

Sie können bilinear/bikubische Interpolation, aber in drei Richtungen (trilinear/tricubic, respectively) nutzen. Es ist ziemlich trivial, wenn Sie verstehen, wie diese Interpolationsformen funktionieren. Weitere Informationen finden Sie unter Tricubic Interpolation on Wikipedia.

Answer 4

Wenn Sie eine einfache lineare Interpolation von diesem Punkt möchte, dann wird der Z-Wert des Mittelpunkts ist nur der Mittelwert der 4 benachbarten Z-Werte, da die Abstände sind symmetrisch in beide Y und X.

Wenn die Abstände nicht symmetrisch sind, aber der Mittelpunkt immer auf den gleichen X- und Y-Linien liegt, können Sie sowohl die Y- als auch die X-Interpolation berechnen, und der Endwert ist der Mittelwert davon.

Also wäre Zc: Zc = (Zx1 + x * (Zx2-Zx1)/(x2-x1) + Zy1 + y * (Zy2-Zy1)/(y2-y1))/2, wobei x und y sind Abstände von x1 und y1.

Answer 5

Suchen Sie nach einer Oberflächeninterpolation oder wäre ein Gitter ausreichend?

Für eine Oberflächeninterpolation ich sehe, daß andere Triangulierung vorgeschlagen hat (zum Beispiel verwenden: http://en.wikipedia.org/wiki/Delaunay_triangulation)

für ein Gitter zu schaffen: einer meiner Kollegen verwendet, um die Wärmeleitungsgleichung (http://en.wikipedia.org/wiki/Heat_equation) die Werte für die Bildpunkte zu berechnen, außerhalb der angegebenen Beispielpunkte. Dies erzeugte extrem realistisch aussehende Geländeoberflächen, und es war trivial, zu parallelisieren.

Answer 6

Ein Problem beim Interpolieren unter Verwendung des in der Frage vorgeschlagenen Schemas, wobei eine Teilmenge nächster Nachbarn aus einer verstreuten Menge ausgewählt wird, ist, dass das Ergebnis nicht kontinuierlich sein muss.

Denken Sie darüber nach. Angenommen, ich würde mich auf einem glatten, kontinuierlichen Pfad durch die (x, y) -Ebene bewegen. Solange sich die 4 nächsten Nachbarn nicht ändern, ist der Interpolant glatt, wie auch immer Sie sich entschieden haben. Irgendwann wird sich diese Teilmenge der nächsten Nachbarn jedoch plötzlich ändern. An diesem Punkt müssen Sie den Interpolanten konsistent über die Grenze haben. Am besten verwenden Sie eine Triangulation des unabhängigen Variablensatzes. Dies stellt einen kontinuierlichen (linearen) Interpolanten innerhalb der konvexen Hülle der Daten sicher. Mit mehr Arbeit können Interpolationen höherer Ordnung auch mit einer Triangulation erreicht werden.

Radiale Basisfunktionen werden normalerweise auch für die Interpolation verwendet, oder Kriging, wenn Sie zufällig in der Geostatistik sind. Da Sie distanzbasierte Methoden untersucht haben, sollten Sie radiale Basisfunktionen in Betracht ziehen. Suchen Sie beispielsweise nach "inverse multiquadric interpolation".