Простой способ интерполирования между точками в трехмерном пространстве для формирования гладкой поверхности

Я пытаюсь создать простой и эффективный способ создания гладкой поверхности, которая пересекает несколько заданных "выборочных" точек.

Для любой точки X, Y на поверхности я идентифицирую до 4 точек выборки в каждом из четырех направлений (следующие более высокие и нижние точки на X, а затем оси Y). Учитывая этот момент, я хочу, чтобы вычислить значение Z, которое интерполирует между 4 точками выборки.

Конечно, алгоритм, заданный положением X, Y любой из 4 точек выборки, должен вывести значение Z для этой точки. Также обратите внимание, что может быть меньше 4 точек выборки.

Я предполагаю, что некоторая функция значений Z для 4 выборочных точек, как-то наоборот, смещена на расстояние до точки выборки, но я не могу понять, как это сделать.

У кого-нибудь есть идеи о простом способе сделать это?

Ответ 1

Вы можете сделать это, построив патчи из сплаймов Catmull-Rom. Эти сплайны попадут в каждую из контрольных точек, и они будут непрерывными в первой производной (хотя и не второй). Я также считаю, что их очень легко работать. Математика проста, и они ведут себя интуитивно с небольшими изменениями в контрольных точках.

На самом высоком уровне вам понадобится 16 очков за патч (на краю вашего набора данных вы можете использовать угловые и краевые точки дважды в одном сплайне).

Во-первых, вам нужно будет интерполировать по точкам p [i] [j] в каждой строке в вашей матрице 4x4, чтобы создать набор из четырех промежуточных контрольных точек q [i]. Вот приблизительный ASCII-эскиз того, что я имею в виду.

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

Теперь вы можете интерполировать между каждой из этих четырех промежуточных контрольных точек, чтобы найти конечную секущую точку на вашей поверхности.

Вот конструкция сплайна Catmull-Rom в четырех точках. В этом примере вы интерполируете между точками p [i-1] и p [i], используя контрольные точки с каждой стороны p [i-2] и p [i + 1]. u - коэффициент интерполяции от нуля до единицы. τ определяется как напряжение на сплайне и влияет на то, насколько плотно ваша шлицевая поверхность соответствует вашим контрольным точкам.

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

ПРИМЕЧАНИЕ. Не сразу понятно, как это сделать в Stackoverflow gui, но u2 и u3 должны представлять квадраты u и u соответственно.

Ответ 2

Вы можете использовать билинейную/бикубическую интерполяцию, но в трех направлениях (трилинейные/трикубические, соответственно). Это довольно тривиально, если вы понимаете, как работают эти формы интерполяции. Для получения дополнительной информации см. Трикубическая интерполяция в Википедии.

Ответ 3

Вы ищете интерполяцию поверхности или достаточно сетки?

Для поверхностной интерполяции я вижу, что другие предложили использовать триангуляции (например, используйте это: http://en.wikipedia.org/wiki/Delaunay_triangulation)

Для создания сетки один из моих коллег использовал уравнение теплоты (http://en.wikipedia.org/wiki/Heat_equation), чтобы вычислить значения для пикселей за пределами данного примеры баллов. Это создавало чрезвычайно реалистичные поверхности поверхности, и было тривиально распараллеливаться.

Ответ 4

Использование патчей catmull-rom

Ответ 5

Если вам нужна простая линейная интерполяция этой точки, то значение Z центральной точки является просто средним из четырех соседних Z-значений, учитывая, что расстояния симметричны как для Y, так и для X.

Если расстояния не симметричны, но центральная точка всегда находится на тех же линиях X и Y, вы можете рассчитать как интерполяции Y, так и X, а конечное значение - среднее из них.

Таким образом, Zc будет: Zc = (Zx1 + x * (Zx2-Zx1)/(x2-x1) + Zy1 + y * (Zy2-Zy1)/(y2-y1))/2, где x и y являются расстояниями от x1 и y1.

Ответ 6

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

Подумайте об этом. Предположим, что я должен двигаться вдоль некоторого гладкого непрерывного пути через плоскость (х, у). Пока 4 ближайших соседа не изменяются, интерполяция будет гладкой, определенной, однако вы решили сделать это. Однако в какой-то момент это подмножество ближайших соседей внезапно изменится. В этот момент вы должны иметь интерполяцию, согласованную через границу. Лучше всего использовать триангуляцию независимого набора переменных. Это обеспечивает непрерывную (линейную) интерполяцию внутри выпуклой оболочки данных. При большей работе интерполяции более высокого порядка также могут быть достигнуты с помощью триангуляции.

Радиальные базовые функции также обычно также используются для интерполяции или Кригинга, если вы попадаете в геостатистику. Поскольку вы изучали методы, основанные на расстоянии, рассмотрите радиальные базовые функции. Например, найдите "обратную мультикадрийную интерполяцию".