三線形補間

三線形補間は、 3次元の規則的なグリッド上で多変数補間を行う手法です。これは、関数の中間点における値を近似します。 $(x,y,z)$ 格子点上の関数データを用いて、局所的な軸方向の直方体内部を線形に補間します。三線形補間は、数値解析、データ解析、コンピュータグラフィックスで頻繁に使用されます。

製剤

周期的な立方格子では、次の値を求めたい。 $x$ 、 $y$ 、 $z$ 一般的には、各座標 (たとえば、 $x$ は厳密には格子点ではなく、ある格子点からある距離にある。 $x_{\text{0}}$ そして次に、 $x_{\text{1}}$ 。させて $x_{\text{d}}$ 下側の格子点からその分数距離だけ離れているとする。 ${\frac {x-x_{0}}{x_{1}-x_{0}}}$ 他の座標についても同様のアプローチを取ってください。

{\begin{aligned}x_{\text{d}}={\frac {x-x_{0}}{x_{1}-x_{0}}}\\y_{\text{d}}={\frac {y-y_{0}}{y_{1}-y_{0}}}\\z_{\text{d}}={\frac {z-z_{0}}{z_{1}-z_{0}}}\end{aligned}}

まず、 $x$ （例えば、立方体の面を「押す」と想像してください。 $C_{0jk}$ 反対側の面は、 $C_{1jk}$ ) 結果として、

{\begin{aligned}c_{00}&=c_{000}(1-x_{\text{d}})+c_{100}x_{\text{d}}\\c_{01}&=c_{001}(1-x_{\text{d}})+c_{101}x_{\text{d}}\\c_{10}&=c_{010}(1-x_{\text{d}})+c_{110}x_{\text{d}}\\c_{11}&=c_{011}(1-x_{\text{d}})+c_{111}x_{\text{d}}\end{aligned}}

どこ $c_{000}$ 関数値の意味 $(x_{0},y_{0},z_{0}).$ 次に、これらの値を補間します（ $y$ 「押し出す」 $C_{i0k}$ に $C_{i1k}$ ) 結果として、

{\begin{aligned}c_{0}&=c_{00}(1-y_{\text{d}})+c_{10}y_{\text{d}}\\c_{1}&=c_{01}(1-y_{\text{d}})+c_{11}y_{\text{d}}\end{aligned}}

最後に、これらの値を補間します $z$ （列に並んで歩く）：

c=c_{0}(1-z_{\text{d}})+c_{1}z_{\text{d}}.

これはその点の予測値を示しており、次のように表すこともできます。 ${\begin{aligned}c&=c_{000}(1-x_{d})(1-y_{d})(1-z_{d})\\&\quad +c_{100}\,x_{d}(1-y_{d})(1-z_{d})\\&\quad +c_{010}(1-x_{d})\,y_{d}(1-z_{d})\\&\quad +c_{110}\,x_{d}\,y_{d}(1-z_{d})\\&\quad +c_{001}(1-x_{d})(1-y_{d})\,z_{d}\\&\quad +c_{101}\,x_{d}(1-y_{d})\,z_{d}\\&\quad +c_{011}(1-x_{d})\,y_{d}\,z_{d}\\&\quad +c_{111}\,x_{d}\,y_{d}\,z_{d}\end{aligned}}$

これにより、三線形補間の結果は、3 つの軸に沿った補間ステップの順序に依存しないことが明らかになります。たとえば、他の順序、 $y$ それから沿って $z$ そして最後に沿って $x$ 同じ値を生成します。

アルゴリズムの可視化

上記の操作は次のように視覚化できます。まず、注目点を取り囲む立方体の8つの角を見つけます。これらの角には次の値があります。 $c_{000}$ 、 $c_{100}$ 、 $c_{010}$ 、 $c_{110}$ 、 $c_{001}$ 、 $c_{101}$ 、 $c_{011}$ 、 $c_{111}$ 。

次に、線形補間を実行します。 $c_{000}$ そして $c_{100}$ 見つける $c_{00}$ 、 $c_{001}$ そして $c_{101}$ 見つける $c_{01}$ 、 $c_{011}$ そして $c_{111}$ 見つける $c_{11}$ 、 $c_{010}$ そして $c_{110}$ 見つける $c_{10}$ 。

次に、補間を行います。 $c_{00}$ そして $c_{10}$ 見つける $c_{0}$ 、 $c_{01}$ そして $c_{11}$ 見つける $c_{1}$ 最後に、値を計算し $c$ 線形補間により $c_{0}$ そして $c_{1}$

実際には、三線形補間は、2つの双線形補間と1つの線形補間を組み合わせたものと同一です。

c\approx l\left(b(c_{000},c_{010},c_{100},c_{110}),\,b(c_{001},c_{011},c_{101},c_{111})\right)

代替アルゴリズム

補間問題の解を記述する別の方法は次のとおりです。

f(x,y,z)\approx a_{0}+a_{1}x+a_{2}y+a_{3}z+a_{4}xy+a_{5}xz+a_{6}yz+a_{7}xyz

ここで係数は線形方程式を解くことによって求められる。

{\begin{aligned}{\begin{bmatrix}1&x_{0}&y_{0}&z_{0}&x_{0}y_{0}&x_{0}z_{0}&y_{0}z_{0}&x_{0}y_{0}z_{0}\\1&x_{1}&y_{0}&z_{0}&x_{1}y_{0}&x_{1}z_{0}&y_{0}z_{0}&x_{1}y_{0}z_{0}\\1&x_{0}&y_{1}&z_{0}&x_{0}y_{1}&x_{0}z_{0}&y_{1}z_{0}&x_{0}y_{1}z_{0}\\1&x_{1}&y_{1}&z_{0}&x_{1}y_{1}&x_{1}z_{0}&y_{1}z_{0}&x_{1}y_{1}z_{0}\\1&x_{0}&y_{0}&z_{1}&x_{0}y_{0}&x_{0}z_{1}&y_{0}z_{1}&x_{0}y_{0}z_{1}\\1&x_{1}&y_{0}&z_{1}&x_{1}y_{0}&x_{1}z_{1}&y_{0}z_{1}&x_{1}y_{0}z_{1}\\1&x_{0}&y_{1}&z_{1}&x_{0}y_{1}&x_{0}z_{1}&y_{1}z_{1}&x_{0}y_{1}z_{1}\\1&x_{1}&y_{1}&z_{1}&x_{1}y_{1}&x_{1}z_{1}&y_{1}z_{1}&x_{1}y_{1}z_{1}\end{bmatrix}}{\begin{bmatrix}a_{0}\\a_{1}\\a_{2}\\a_{3}\\a_{4}\\a_{5}\\a_{6}\\a_{7}\end{bmatrix}}={\begin{bmatrix}c_{000}\\c_{100}\\c_{010}\\c_{110}\\c_{001}\\c_{101}\\c_{011}\\c_{111}\end{bmatrix}},\end{aligned}}

結果として

{\begin{aligned}a_{0}={}&{\frac {-c_{000}x_{1}y_{1}z_{1}+c_{001}x_{1}y_{1}z_{0}+c_{010}x_{1}y_{0}z_{1}-c_{011}x_{1}y_{0}z_{0}}{(x_{0}-x_{1})(y_{0}-y_{1})(z_{0}-z_{1})}}+{}\\&{\frac {c_{100}x_{0}y_{1}z_{1}-c_{101}x_{0}y_{1}z_{0}-c_{110}x_{0}y_{0}z_{1}+c_{111}x_{0}y_{0}z_{0}}{(x_{0}-x_{1})(y_{0}-y_{1})(z_{0}-z_{1})}},\\[4pt]a_{1}={}&{\frac {c_{000}y_{1}z_{1}-c_{001}y_{1}z_{0}-c_{010}y_{0}z_{1}+c_{011}y_{0}z_{0}}{(x_{0}-x_{1})(y_{0}-y_{1})(z_{0}-z_{1})}}+{}\\&{\frac {-c_{100}y_{1}z_{1}+c_{101}y_{1}z_{0}+c_{110}y_{0}z_{1}-c_{111}y_{0}z_{0}}{(x_{0}-x_{1})(y_{0}-y_{1})(z_{0}-z_{1})}},\\[4pt]a_{2}={}&{\frac {c_{000}x_{1}z_{1}-c_{001}x_{1}z_{0}-c_{010}x_{1}z_{1}+c_{011}x_{1}z_{0}}{(x_{0}-x_{1})(y_{0}-y_{1})(z_{0}-z_{1})}}+{}\\&{\frac {-c_{100}x_{0}z_{1}+c_{101}x_{0}z_{0}+c_{110}x_{0}z_{1}-c_{111}x_{0}z_{0}}{(x_{0}-x_{1})(y_{0}-y_{1})(z_{0}-z_{1})}},\\[4pt]a_{3}={}&{\frac {c_{000}x_{1}y_{1}-c_{001}x_{1}y_{1}-c_{010}x_{1}y_{0}+c_{011}x_{1}y_{0}}{(x_{0}-x_{1})(y_{0}-y_{1})(z_{0}-z_{1})}}+{}\\&{\frac {-c_{100}x_{0}y_{1}+c_{101}x_{0}y_{1}+c_{110}x_{0}y_{0}-c_{111}x_{0}y_{0}}{(x_{0}-x_{1})(y_{0}-y_{1})(z_{0}-z_{1})}},\\[4pt]a_{4}={}&{\frac {-c_{000}z_{1}+c_{001}z_{0}+c_{010}z_{1}-c_{011}z_{0}+c_{100}z_{1}-c_{101}z_{0}-c_{110}z_{1}+c_{111}z_{0}}{(x_{0}-x_{1})(y_{0}-y_{1})(z_{0}-z_{1})}},\\[4pt]a_{5}=&{\frac {-c_{000}y_{1}+c_{001}y_{1}+c_{010}y_{0}-c_{011}y_{0}+c_{100}y_{1}-c_{101}y_{1}-c_{110}y_{0}+c_{111}y_{0}}{(x_{0}-x_{1})(y_{0}-y_{1})(z_{0}-z_{1})}},\\[4pt]a_{6}={}&{\frac {-c_{000}x_{1}+c_{001}x_{1}+c_{010}x_{1}-c_{011}x_{1}+c_{100}x_{0}-c_{101}x_{0}-c_{110}x_{0}+c_{111}x_{0}}{(x_{0}-x_{1})(y_{0}-y_{1})(z_{0}-z_{1})}},\\[4pt]a_{7}={}&{\frac {c_{000}-c_{001}-c_{010}+c_{011}-c_{100}+c_{101}+c_{110}-c_{111}}{(x_{0}-x_{1})(y_{0}-y_{1})(z_{0}-z_{1})}}.\end{aligned}}

外部リンク

NASAの擬似コードは、反復逆三線形補間（頂点とCの値が与えられたときにXd、Yd、Zdを求める）を記述しています。
ポール・バーク著『補間法』（1999年）。二進論理に基づいた、非常に巧妙かつシンプルな三線形補間法を紹介しており、任意の次元（四線形、五線形など）に拡張可能。
Kenwright、「自由形状四面体変形」。国際ビジュアルコンピューティングシンポジウム。Springer International Publishing、2015年。

三線形補間

関連メソッド

製剤

アルゴリズムの可視化

代替アルゴリズム

関連項目

外部リンク

関連するトピック

双線形補間とそれに続く

線形補間

3次元の

規則的なグリッド