三角形插值

Question

我有一个单位直角三角形，在三个顶点处有一个值。 我需要插值来找到三角形内部的一个点的值。 搜索了几个小时，没有找到确切告诉我如何做这件事的方法。 以下是我最接近的尝试，它其实相当接近但还不够正确 -

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

v1、v2和v3是三角形的三个顶点的值。 （x，y）是您要查找其值的三角形内部的点。

任何一种方法都可以帮助我。它不必是一个单位/直角三角形。

更新的信息： 我有一个均匀分布的点网格和每个点的值。 我用网格上最近的三个点构成一个三角形。 这里有一张图片来说明它 -
所以我必须在5、3和7之间进行插值，以找到x的值。 该点也可能在另一个三角形内，这意味着您需要在5、7和正方形左下角的值之间进行插值。

在我展示的代码中，v1 = 5，v2 = 3，v3 = 7。
x是“x”方向上的分数距离（范围为[0-1]），y是“y”方向上的分数距离。
在图片的例子中，x可能大约为0.75，y可能为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;

它们都接近我所需要的，但显然还不是完全正确的。

- Frobot

---

我会使用线性/双线性插值。最近邻算法不可行。 - Frobot

这里三角形真的很重要吗？四点插值可以吗？ - rsaxvc

我通常使用4点双线性插值，但现在看来我可以通过使用三角形来大大提高速度。我通常在v1和v2之间进行插值，然后在v3和v4之间进行插值，然后再在这两个新值之间进行插值以得到最终值。我想用一个类似的方法，但是使用三角形。 - Frobot

这会显示出痕迹 - 这对您可接受吗？ - rsaxvc

工件通常不会有问题，除非它们太大。 - Frobot

Answer 1

你应该使用重心坐标。这里有一篇非常详细的文章，讨论了替代方案以及为什么重心坐标是最好的：CodePlea - 插值三角形

基本上，权重最终会像这样：

- reneekk

---

这应该是被接受的答案，因为它纯粹是2D而不是3D。 - clabe45

公式也适用于外推。 - fchen

Answer 2

实际上，最简单和最健壮的解决方案基于重心坐标 -

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

- titanae

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;

- Frobot

---

你能否发布一张结果的照片以供比较？ - rsaxvc

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

- Dan

---

所以假设这将得到正确的值，我还必须考虑那些不在右上三角形中而是在正方形的左下部分的点。所以我还需要一个v4。我尝试了这个 - if (x > y) //如果该点在右上三角形中 return (1 - x) * v1 + (x - y) * v2 + y * v3; else //如果该点在左下三角形中 return (1 - x) * v1 + (x - y) * v4 + y * v3; 但它没有起作用。 - Frobot

你想要生成什么样的梯度？如果你想基于一个正方形来做，那就有点复杂了，因为 d/dx = (v2 - v1) (1 - y) + (v3 - v4) y 和 d/dy = (v3 - v2) x + (v4 - v1) (1 - x)。但这仍然是可能的。 - Dan

我不太确定你在问什么，但我正在制作一个平滑噪声函数。我已经使用完整的正方形和双线性插值使其工作，类似于Perlin噪声，但我正在尝试改用三角形来实现它。 - Frobot

我找到了一个非常接近的方法，但是伪影相当严重。 - Frobot

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 )

我认为这也会生成一个voronoi图

- rsaxvc

---

我需要某种线性插值，因为最近邻居法只会产生大块颜色方块。 - Frobot

不是正方形。只有在使用正方形位置的采样点，并且您指定了三角形时，它才会生成正方形。 - rsaxvc

抱歉，我的意思是它将生成大而实心的彩色三角形*。 - Frobot

不会生成三角形，但会有大的纯色区域 - 这将生成四边形。对于一个点，它将使两条边成为三角形外边缘的一半，并且是到其他点的两条垂直平分线。 - rsaxvc

啊，好的。我还没有测试过它，但关键是它不适合这项工作。 - Frobot