Trilineární interpolace - Trilinear interpolation

Trilineární interpolace je metoda vícerozměrná interpolace na 3 dimenzionální pravidelná mřížka. Přibližuje hodnotu funkce v mezilehlém bodě ${ displaystyle (x, y, z)}$ v místním axiálním obdélníku hranol lineárně pomocí funkčních dat na mřížových bodech. Pro svévolné, nestrukturovaná síť (jak se používá v konečný element analýza), musí být použity jiné metody interpolace; pokud jsou všechny prvky sítě čtyřstěn (3D jednoduchosti ), pak barycentrické souřadnice poskytnout přímý postup.

Trilineární interpolace se často používá v numerická analýza, analýza dat, a počítačová grafika.

Ve srovnání s lineární a bilineární interpolací

Trilineární interpolace je rozšířením lineární interpolace, která působí v prostorách s dimenze ${ displaystyle D = 1}$ , a bilineární interpolace, který pracuje s dimenzí ${ displaystyle D = 2}$ , do dimenze ${ displaystyle D = 3}$ . Všechna tato interpolační schémata používají polynomy řádu 1, což dává přesnost řádu 2, a to vyžaduje ${ displaystyle 2 ^ {D} = 8}$ sousední předdefinované hodnoty obklopující interpolační bod. Existuje několik způsobů, jak dospět k trilineární interpolaci, která je ekvivalentní trojrozměrné tenzor B-spline interpolace řádu 1 a trilineární interpolační operátor je také tenzorovým součinem 3 lineárních interpolačních operátorů.

Metoda

Osm rohových bodů na krychli obklopujících interpolační bod C.

Zobrazení 3D interpolace

Geometrická vizualizace trilineární interpolace. Součin hodnoty v požadovaném bodě a celého objemu se rovná součtu součinů hodnoty v každém rohu a částečného objemu úhlopříčně naproti rohu.

Na periodické a kubické mřížce, nechť ${ displaystyle x _ { text {d}}}$ , ${ displaystyle y _ { text {d}}}$ , a ${ displaystyle z _ { text {d}}}$ být rozdíly mezi každou z ${ displaystyle x}$ , ${ displaystyle y}$ , ${ displaystyle z}$ a menší souřadnice související, to je:

{ displaystyle { 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 {zarovnáno}}}

kde ${ displaystyle x_ {0}}$ označuje mřížkový bod níže ${ displaystyle x}$ , a ${ displaystyle x_ {1}}$ označuje výše uvedený mřížkový bod ${ displaystyle x}$ a podobně pro ${ displaystyle y_ {0}, y_ {1}, z_ {0}}$ a ${ displaystyle z_ {1}}$ .

Nejprve spolu interpolujeme ${ displaystyle x}$ (představte si, že „tlačíme“ na tvář krychle definovanou znakem ${ displaystyle C_ {0jk}}$ na protilehlou tvář, definovanou ${ displaystyle C_ {1jk}}$ ), dávat:

{ displaystyle { 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}}}

Kde ${ displaystyle c_ {000}}$ znamená hodnotu funkce ${ displaystyle (x_ {0}, y_ {0}, z_ {0}).}$ Pak tyto hodnoty interpolujeme (spolu ${ displaystyle y}$ „tlačí“ z ${ displaystyle C_ {i0k}}$ na ${ displaystyle C_ {i1k}}$ ), dávat:

{ displaystyle { 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 {zarovnáno}}}

Nakonec tyto hodnoty interpolujeme ${ displaystyle z}$ (procházení linií):

{ displaystyle c = c_ {0} (1-z _ { text {d}}) + c_ {1} z _ { text {d}}.}

To nám dává předpokládanou hodnotu bodu.

Výsledek trilineární interpolace je nezávislý na pořadí kroků interpolace podél tří os: jakýkoli jiný řád, například podél ${ displaystyle x}$ , pak spolu ${ displaystyle y}$ a nakonec spolu ${ displaystyle z}$ , produkuje stejnou hodnotu.

Výše uvedené operace lze vizualizovat takto: Nejprve najdeme osm rohů krychle, které obklopují náš bod zájmu. Tyto rohy mají hodnoty ${ displaystyle c_ {000}}$ , ${ displaystyle c_ {100}}$ , ${ displaystyle c_ {010}}$ , ${ displaystyle c_ {110}}$ , ${ displaystyle c_ {001}}$ , ${ displaystyle c_ {101}}$ , ${ displaystyle c_ {011}}$ , ${ displaystyle c_ {111}}$ .

Dále provedeme lineární interpolaci mezi ${ displaystyle c_ {000}}$ a ${ displaystyle c_ {100}}$ najít ${ displaystyle c_ {00}}$ , ${ displaystyle c_ {001}}$ a ${ displaystyle c_ {101}}$ najít ${ displaystyle c_ {01}}$ , ${ displaystyle c_ {011}}$ a ${ displaystyle c_ {111}}$ najít ${ displaystyle c_ {11}}$ , ${ displaystyle c_ {010}}$ a ${ displaystyle c_ {110}}$ najít ${ displaystyle c_ {10}}$ .

Nyní provádíme interpolaci mezi ${ displaystyle c_ {00}}$ a ${ displaystyle c_ {10}}$ najít ${ displaystyle c_ {0}}$ , ${ displaystyle c_ {01}}$ a ${ displaystyle c_ {11}}$ najít ${ displaystyle c_ {1}}$ . Nakonec vypočítáme hodnotu ${ displaystyle c}$ lineární interpolací ${ displaystyle c_ {0}}$ a ${ displaystyle c_ {1}}$

V praxi je trilineární interpolace identická se dvěma bilineární interpolace v kombinaci s lineární interpolací:

{ displaystyle c přibližně l vlevo (b (c_ {000}, c_ {010}, c_ {100}, c_ {110}), , b (c_ {001}, c_ {011}, c_ {101 }, c_ {111}) vpravo)}

Alternativní algoritmus

Alternativním způsobem, jak napsat řešení problému s interpolací, je

{ displaystyle f (x, y, z) přibližně a_ {0} + a_ {1} x + a_ {2} y + a_ {3} z + a_ {4} xy + a_ {5} xz + a_ { 6} yz + a_ {7} xyz}

kde jsou koeficienty nalezeny řešením lineárního systému

{ displaystyle { 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 {zarovnáno}}}

přináší výsledek

{ displaystyle { 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})}}, [4 b. ] 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 {zarovnáno}}}

Viz také

externí odkazy

pseudokód od NASA, popisuje iterační inverzní trilineární interpolaci (vzhledem k vrcholům a hodnotě C find Xd, Yd a Zd).
Paul Bourke, Interpolační metody, 1999. Obsahuje velmi chytrou a jednoduchou metodu k nalezení trilineární interpolace, která je založena na binární logice a lze ji rozšířit na jakoukoli dimenzi (Tetralineární, Pentalineární, ...).
Kenwright, volná forma čtyřstěnné deformace. Mezinárodní sympozium o vizuálních počítačích. Springer International Publishing, 2015 [1].