Интерполяция треугольника

Question

У меня есть единичный правый треугольник и значение в каждой из трех вершин. Мне нужно интерполировать, чтобы найти значение в точке внутри треугольника. Часы поиска не показали ничего, что на самом деле говорит мне, как это сделать. Вот моя ближайшая попытка, которая на самом деле довольно близко, но не совсем верно -

   result = 
       v1 * (1 - x) * (1 - y) + 
       v2 * x * (1 - y) + 
       v3 * x * y; 

v1, v2, v3 и являются значениями в 3-х вершин треугольника. (x, y) - это точка в треугольнике, которую вы пытаетесь найти значение.

Любой способ поможет мне здесь. Это не обязательно должен быть единичный/правый треугольник.

Обновилась информация: У меня есть сетка равномерно расположенных точек и значение в каждой точке. Я делаю треугольник из ближайших 3 точек на сетке. Вот изображение, чтобы проиллюстрировать это -
Поэтому я должен интерполировать между 5, 3 и 7, чтобы найти значение x. Точка также может быть внутри другого треугольника, то есть вы должны интерполировать между 5, 7 и значением нижнего левого угла квадрата.

В коде я показал, v1 = 5, V2 = 3, v3 = 7.
х дробная расстояние (диапазон [0-1]) в "х" направлении, а у есть дробная расстояние в направлении «y».
В примере на картинке, в х, вероятно, будет около 0,75, а у будет составлять около 0,2

Вот мои близкие попытки -

Создано с помощью -

 if (x > y) //if x > y then the point is in the upper right triangle 
      return 
       v1 * (1 - x) * (1 - y) + 
       v2 * x * (1 - y) + 
       v3 * x * y; 
     else //bottom left triangle 
      return 
       v1 * (1 - x) * (1 - y) + 
       v4 * (1 - x) * y + 
       v3 * x * y; 

И еще одна попытка -

Создано с использованием -

if (x > y) 
      return 
       (1 - x) * v1 + (x - y) * v2 + y * v3; 
     else 
      return 
       (1 - y) * v1 + (y - x) * v4 + x * v3; 

Они оба близки к тому, что мне нужно, но явно не совсем правильно.

Answer 1

Я задал этот 3-х лет назад и до сих пор работали на пути, чтобы сделать это. Я считаю, что это невозможно, если не использовать равносторонний треугольник. Вот достойный способ сделать это с помощью барицентрических координат, а затем добавить технику, которая избавится от большинства артефактов. v1, v2, v3 - значения в трех точках треугольника. x, y - точка, в которой вы хотите найти значение.

if (x > y) 
     { 
      b1 = -(x - 1); 
      b2 = (x - 1) - (y - 1); 
      b3 = 1 - b1 - b2; 
     } 
     else 
     { 
      b1 = -(y - 1); 
      b2 = -((x - 1) - (y - 1)); 
      b3 = 1 - b1 - b2; 
     } 

     float 
      abs = x - y; 
     if (abs < 0) abs *= -1; 
     if (abs < 0.25f) 
     { 
      abs = 0.25f - abs; 
      abs *= abs; 
      b1 -= abs; 
      b3 -= abs; 
     } 

     b1 *= b1; 
     b2 *= b2; 
     b3 *= b3; 
     float fd = 1/(b1 + b2 + b3); 
     b1 *= fd; 
     b2 *= fd; 
     b3 *= fd; 

     return 
       v1 * b1 + 
       v2 * b2 + 
       v3 * b3; 

Answer 2

Итак, мы будем делать линейную интерполяцию, предполагая, что градиент является постоянным по отношению к x и y. d/dx = v2 - v1 и d/dy = v3 - v2, и f(0,0) = v1. Мы имеем простое двумерное дифференциальное уравнение.

d{f(x,y)} = (v2 - v1)*dx 
f(x,y) = (v2 - v1)*x + g(y) 
d{f(x,y)} = g'(y) = (v3 - v2)*dy 
g(y) = (v3 - v2)*y + C 
f(x,y) = (v2 - v1)*x + (v3 - v2)*y + C 
f(0,0) = v1 = (v2 - v1)*0 + (v3 - v2)*0 + C = C 
f(x,y) = (v2 - v1)*x + (v3 - v2)*y + v1 

или в терминах v1 v2 и v3

f(x,y) = (1 - x)*v1 + (x - y)*v2 + y*v3 

Если вы хотите сделать это в квадрате для четырех вершин, как описано выше, v4 в левой нижней точке х = 0 у = 1 , вот условие: d/dx = (v2 - v1) (1 - y) + (v3 - v4) y, d/dy = (v3 - v2) x + (v4 - v1) (1 - x), f(0,0) = v1

d/dx = (v2 - v1) (1 - y) + (v3 - v4) y 
f(x,y) = (v2 - v1) (1 - y) x + (v3 - v4) y x + g(y) 
d/dy = (v3 - v2) x + (v4 - v1) (1 - x) = -(v2 - v1) x + (v3 - v4) x + g'(y) 
v3 - v2 + (v4 - v1)/x + v4 - v1 = -v2 + v1 + v3 - v4 + g'(y)/x 
(v4 - v1)/x + 2*(v4 - v1) = g'(y)/x 
g'(y) = (v4 - v1) + 2 x (v4 - v1) 
g(y) = (v4 - v1) (1 + 2 x) y + C 
f(x,y) = (v2 - v1) (1 - y) x + (v3 - v4) y x + (v4 - v1) (1 + 2 x) y + C 
f(0,0) = (v2 - v1) (1 - 0) 0 + (v3 - v4) 0 0 + (v4 - v1) (1 + 2 0) 0 + C = v1 
f(x,y) = (v2 - v1) (1 - y) x + (v3 - v4) y x + (v4 - v1) (1 + 2 x) y + v1 

Answer 3

Вот некоторые псевдокоды для ближайших соседей:

if(dist(p, p1) <= dist(p, p2) && dist(p, p1) <= dist(p, p3)) 
    return val(p1) 
if(dist(p, p2) <= dist(p, p3) && dist(p, p2) <= dist(p, p1)) 
    return val(p2) 
if(dist(p, p3) <= dist(p, p1) && dist(p, p3) <= dist(p, p2)) 
    return val(p3) 

Я думаю, что это также создает диаграммы Вороного

Answer 4

На самом деле самое простое и надежное решение основано на барицентрических координатах -

http://answers.unity3d.com/questions/383804/calculate-uv-coordinates-of-3d-point-on-plane-of-m.html

Answer 5

Вы должны использовать барицентрические координаты. Существует очень тщательное рецензия здесь также обсуждаются альтернативные решения и почему барицентрические координаты являются лучшими: CodePlea - Interpolating in a Triangle

В основном, вес будет в конечном итоге выглядит так: