Трилинейная интерполяция - Trilinear interpolation

Трилинейная интерполяция это метод многомерная интерполяция на 3-х мерный регулярная сетка. Он приближает значение функции в промежуточной точке ${ Displaystyle (х, у, г)}$ в пределах местного осевого прямоугольного призма линейно, используя функциональные данные о точках решетки. Для произвольного неструктурированная сетка (как используется в заключительный элемент анализ), необходимо использовать другие методы интерполяции; если все элементы сетки тетраэдры (3D симплексы ), тогда барицентрические координаты обеспечить простую процедуру.

Трилинейная интерполяция часто используется в численный анализ, анализ данных, и компьютерная графика.

По сравнению с линейной и билинейной интерполяцией

Трилинейная интерполяция является продолжением линейная интерполяция, который работает в пространствах с измерение ${ displaystyle D = 1}$ , и билинейная интерполяция, который оперирует размерностью ${ displaystyle D = 2}$ , к размеру ${ displaystyle D = 3}$ . Все эти схемы интерполяции используют многочлены порядка 1, что дает точность порядка 2, и для этого требуется ${ displaystyle 2 ^ {D} = 8}$ смежные предварительно определенные значения, окружающие точку интерполяции. Есть несколько способов получить трилинейную интерполяцию, которая эквивалентна трехмерной интерполяции. тензор B-шлиц интерполяция порядка 1, и оператор трилинейной интерполяции также является тензорным произведением 3 операторов линейной интерполяции.

Метод

Восемь угловых точек на кубе, окружающем точку интерполяции C

Изображение трехмерной интерполяции

Геометрическая визуализация трилинейной интерполяции. Произведение значения в желаемой точке и всего объема равно сумме произведений значения в каждом углу и частичного объема по диагонали напротив угла.

На периодической и кубической решетке пусть ${ displaystyle x _ { text {d}}}$ , ${ displaystyle y _ { text {d}}}$ , и ${ displaystyle z _ { text {d}}}$ быть различиями между каждым из ${ displaystyle x}$ , ${ displaystyle y}$ , ${ displaystyle z}$ и меньшая координата, то есть:

{ displaystyle { begin {align} 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}}} конец {выровнено}}}

где ${ displaystyle x_ {0}}$ указывает точку решетки ниже ${ displaystyle x}$ , и ${ displaystyle x_ {1}}$ указывает точку решетки над ${ displaystyle x}$ и аналогично для ${ displaystyle y_ {0}, y_ {1}, z_ {0}}$ и ${ displaystyle z_ {1}}$ .

Сначала мы интерполируем по ${ displaystyle x}$ (представьте, что мы "толкаем" грань куба, определяемую ${ displaystyle C_ {0jk}}$ к противоположному лицу, определяемому ${ displaystyle C_ {1jk}}$ ), дающий:

{ displaystyle { begin {align} 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 _ { текст {д}} end {выровненный}}}

куда ${ displaystyle c_ {000}}$ означает значение функции ${ displaystyle (x_ {0}, y_ {0}, z_ {0}).}$ Затем мы интерполируем эти значения (по ${ displaystyle y}$ , "толкая" от ${ displaystyle C_ {i0k}}$ к ${ displaystyle C_ {i1k}}$ ), дающий:

{ displaystyle { begin {align} 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 {выровнено}}}

Наконец, мы интерполируем эти значения по ${ displaystyle z}$ (проходя по очереди):

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

Это дает нам прогнозируемое значение для точки.

Результат трилинейной интерполяции не зависит от порядка шагов интерполяции по трем осям: любого другого порядка, например, по ${ displaystyle x}$ , затем по ${ displaystyle y}$ , и, наконец, вместе ${ displaystyle z}$ , дает то же значение.

Вышеупомянутые операции можно визуализировать следующим образом: Сначала мы находим восемь углов куба, которые окружают нашу точку интереса. Эти углы имеют значения ${ displaystyle c_ {000}}$ , ${ displaystyle c_ {100}}$ , ${ displaystyle c_ {010}}$ , ${ displaystyle c_ {110}}$ , ${ displaystyle c_ {001}}$ , ${ displaystyle c_ {101}}$ , ${ displaystyle c_ {011}}$ , ${ displaystyle c_ {111}}$ .

Далее мы выполняем линейную интерполяцию между ${ displaystyle c_ {000}}$ и ${ displaystyle c_ {100}}$ найти ${ displaystyle c_ {00}}$ , ${ displaystyle c_ {001}}$ и ${ displaystyle c_ {101}}$ найти ${ displaystyle c_ {01}}$ , ${ displaystyle c_ {011}}$ и ${ displaystyle c_ {111}}$ найти ${ displaystyle c_ {11}}$ , ${ displaystyle c_ {010}}$ и ${ displaystyle c_ {110}}$ найти ${ displaystyle c_ {10}}$ .

Теперь делаем интерполяцию между ${ displaystyle c_ {00}}$ и ${ displaystyle c_ {10}}$ найти ${ displaystyle c_ {0}}$ , ${ displaystyle c_ {01}}$ и ${ displaystyle c_ {11}}$ найти ${ displaystyle c_ {1}}$ . Наконец, мы вычисляем значение ${ displaystyle c}$ с помощью линейной интерполяции ${ displaystyle c_ {0}}$ и ${ displaystyle c_ {1}}$

На практике трилинейная интерполяция идентична двух билинейная интерполяция в сочетании с линейной интерполяцией:

{ displaystyle c приблизительно l left (b (c_ {000}, c_ {010}, c_ {100}, c_ {110}), , b (c_ {001}, c_ {011}, c_ {101) }, c_ {111}) right)}

Альтернативный алгоритм

Альтернативный способ написать решение задачи интерполяции:

{ displaystyle f (x, y, z) приблизительно a_ {0} + a_ {1} x + a_ {2} y + a_ {3} z + a_ {4} xy + a_ {5} xz + a_ { 6} yz + a_ {7} xyz}

где коэффициенты находятся из решения линейной системы

{ displaystyle { begin {align} { 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 {выравнивается}}}

дающий результат

{ displaystyle { begin {align} 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} = {} & { гидроразрыв {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 {align}}}

Смотрите также

внешние ссылки

псевдокод от НАСА, описывает итеративную обратную трилинейную интерполяцию (по вершинам и значению C найти Xd, Yd и Zd).
Поль Бурк, Методы интерполяции, 1999. Содержит очень умный и простой метод поиска трилинейной интерполяции, который основан на бинарной логике и может быть расширен до любого измерения (тетралинейной, пенталинейной, ...).
Кенрайт, Деформация тетраэдра произвольной формы. Международный симпозиум по визуальным вычислениям. Springer International Publishing, 2015 г. [1].