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

Question

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

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

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

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

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

В коде, который я показал, v1 = 5, v2 = 3, v3 = 7.
x - дробное расстояние (диапазон [0-1]) в направлении «x», а y - дробное расстояние в направлении «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

Вы должны использовать барицентрические координаты.Здесь приведена очень тщательная запись, в которой также обсуждаются альтернативные решения и почему барицентрические координаты лучше всего: CodePlea - интерполяция в треугольнике

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

Answer 2

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

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

Answer 3

Я спросил об этом 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 4

Хорошо, мы выполним линейную интерполяцию, предполагая, что градиент постоянен относительно 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 в левом нижнем углу при x = 0 y = 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 5

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

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 )

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