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

Question

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

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

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

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

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

Answer 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

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

Вот конструкция сплайна Катмулла-Рома через четыре точки. В этом примере вы интерполируете между точками 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, но u2 и u3 должны представлять u в квадрате и u куб соответственно.

Answer 2

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

Answer 3

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

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

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

Answer 4

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

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

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

Answer 5

Если вы хотите простую линейную интерполяцию этой точки, то значение Z центральной точки является просто средним значением 4-х соседних значений 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.

Answer 6

Используйте патчи Catmull-rom