另一种(Yet Another)三角形线性插值方法

栏目: 后端 · 发布时间: 7年前

内容简介：本文简述了一种三角形线性插值的方法(本文仅讨论二维情况)给定一个三角形的顶点坐标(问题说的有些抽象,给张图会清晰明了一些,图中的

本文简述了一种三角形线性插值的方法(本文仅讨论二维情况)

插值方法

如何求解呢?一般我们是采用比例面积的方法,见下图(图中 a0, a1 和 a2 分别代表三个分割三角形的面积):

另一种(Yet Another)三角形线性插值方法

图中 a0 占三角形整体面积的比例代表 V2 ( P2 对应的数值)占 V 的比例, a1 占三角形整体面积的比例代表 V1 ( P1 对应的数值)占 V 的比例, 而 a2 占三角形整体面积的比例则代表 V0 ( P0 对应的数值)占 V 的比例,假设三角形的整体面积为 a , 则我们有:

$\begin{aligned} V & = \dfrac{a_0}{a} * V_2 + \dfrac{a_1}{a} * V_1 + \dfrac{a_2}{a} * V_0 \\ & = (a_0 * V_2 + a_1 * V_1 + a_2 * V_0) / a \end{aligned}$

接下来的问题就是如何根据三角形的顶点求解三角形的面积了,这里我们直接给出结论,有兴趣的朋友可以从这里开始了解,方法就是使用叉积 :

假设三角形的三个顶点分别为 P0, P1 和 P2 , 则三角形面积 a 的计算公式为:

$a = \dfrac{1}{2} * | (P_1 - P_0) \times (P_2 - P_0) |$

如果 P0 的坐标为 <x0, y0> , P1 的坐标为 <x1, y1> , P2 的坐标为 <x2, y2> ,则上面的公式可表达为:

$\begin{aligned} a & = \dfrac{1}{2} * | (P_1 - P_0) \times (P_2 - P_0) | \\ & = \dfrac{1}{2} * |(<x_1, y_1> - <x_0, y_0>) \times (<x_2, y_2> - <x_0, y_0>) | \\ & = \dfrac{1}{2} * |(<x_1 - x_0, y_1 - y_0>) \times (<x_2 - x_0, y_2 - y_0>) | \\ & = \dfrac{1}{2} * |(x_1 - x_0) * (y_2 - y_0) - (x_2 - x_0) * (y_1 - y_0) | \end{aligned}$ = ∗ ∣ ( P 1 − P 0 ) × ( P 2 − P 0 ) ∣ = ∗ ∣ ( < x 1 , y 1 > − < x 0 , y 0 > ) × ( < x 2 , y 2 > − < x 0 , y 0 > ) ∣ = ∗ ∣ ( < x 1 − x 0 , y 1 − y 0 > ) × ( < x 2 − x 0 , y 2 − y 0 > ) ∣ = ∗ ∣ ( x 1 − x 0 ) ∗ ( y 2 − y 0 ) − ( x 2 − x 0 ) ∗ ( y 1 − y 0 ) ∣

这里需要说明的一点是,二维向量实际上是没有叉积定义的,但是我们可以将二维坐标点看做是三维坐标点(第三维取 0 即可)来进行求解,更多细节还是请参看这里 .

讲到这里,我们便可以进行实现了,参考代码如下:

public struct Value2<T>
{
    public float x;
    public float y;
    public T v;

    public Vector2 Vector
    {
        get
        {
            return new Vector2(x, y);
        }
    }

    public Value2(float x, float y, T v)
    {
        this.x = x;
        this.y = y;
        this.v = v;
    }
}

public static float Cross(Vector2 v0, Vector2 v1)
{
    return v0.x * v1.y - v1.x * v0.y;
}

public static float TriangleArea(Vector2 v0, Vector2 v1)
{
    return 0.5f * Math.Abs(Cross(v0, v1));
}

public static float TriangleLerp(Value2f val0, Value2f val1, Value2f val2, Vector2 p)
{
    var v01 = val1.Vector - val0.Vector;
    var v02 = val2.Vector - val0.Vector;
    var v0p = p - val0.Vector;

    var a = TriangleArea(v01, v02);
    Debug.Assert(a > 0, "[MathUtil]Error to do triangle Lerp, seems vertexes collinear ...");
    
    var a0 = TriangleArea(v01, v0p);
    var a1 = TriangleArea(v0p, v02);
    var a2 = a - a0 - a1;

    return (val2.v * a0 + val1.v * a1 + val0.v * a2) / a;
}

另一种(Yet Another)插值方法

实际上我还尝试了一种类似于双线性插值的求解方法,发现也是可行的,参考下图:

另一种(Yet Another)三角形线性插值方法

其中的虚线线段平行于向量 P2 - P1 (虚线取用其他线段也是可行的,只是计算上不方便),只要我们求解出 P1’ 的对应数值 V1’ , P2’ 的对应数值 v2’ ,以及子线段( P1’ 至 P )占总线段( P1’ 至 P2’ )的比例 t ,则 P 点对应的数值 V 便可以用简单的线性插值来求解了:

$V = (1 - t) * V_1' + t * V_2'$

我们可以采用解析法来求解上面所需的 V1’ , V2’ 和 t , 参考下图:

另一种(Yet Another)三角形线性插值方法

我们设红色向量部分( P1’ - P )等于 t1 * (P2 - P1) ,黄色向量部分( P1’ - P0 )等于 t2 * (P1 - P0) ,由于相似三角形对应边成比例的关系,蓝色向量部分( P2’ - P0 )的比例系数也为 t2 ,类似的,向量 P2’ - P1’ 相对与向量 P2 - P1 的比例系数同样也为 t2 .

我们知道:

$\begin{aligned} & P_1' - P_0 = (P - P_0) + (P_1' - P) \implies \\ & t_2 * (P_1 - P_0) = (P - P_0) + t_1 * (P_2 - P_1) \end{aligned}$

并且 P0 的坐标为 <x0, y0> , P1 的坐标为 <x1, y1> , P2 的坐标为 <x2, y2> , P 的坐标为 <x, y>

则有:

$\left\{ \begin{aligned} t_2 * (x_1 - x_0) & = x - x_0 + t_1 * (x_2 - x_1) \\ t_2 * (y_1 - y_0) & = y - y_0 + t_1 * (y_2 - y_1) \end{aligned} \right.$ { t 2 ∗ ( x 1 − x 0 ) t 2 ∗ ( y 1 − y 0 ) = x − x 0 + t 1 ∗ ( x 2 − x 1 ) = y − y 0 + t 1 ∗ ( y 2 − y 1 )

求解可得:

$\left\{ \begin{aligned} t_1 & = \dfrac{(x_1 - x_0) * (y - y_0) - (x - x_0) * (y_1 - y_0)}{(x_2 - x_1) * (y_1 - y_0) - (x_1 - x_0) * (y_2 - y_1)} = \dfrac{(P_1 - P_0) \times (P - P_0)}{(P_2 - P_1) \times (P_1 - P_0)} \\ t_2 & = \dfrac{(x - x_0) + t_1 * (x_2 - x_1)}{x_1 - x_0} or \dfrac{(y - y_0) + t_1 * (y_2 - y_1)}{y_1 - y_0} \end{aligned} \right.$ ⎩ ⎪ ⎪ ⎨ ⎪ ⎪ ⎧ t 1 t 2 = ( x 2 − x 1 ) ∗ ( y 1 − y 0 ) − ( x 1 − x 0 ) ∗ ( y 2 − y 1 ) ( x 1 − x 0 ) ∗ ( y − y 0 ) − ( x − x 0 ) ∗ ( y 1 − y 0 ) = ( P 2 − P 1 ) × ( P 1 − P 0 ) ( P 1 − P 0 ) × ( P − P 0 ) = x 1 − x 0 ( x − x 0 ) + t 1 ∗ ( x 2 − x 1 ) o r y 1 − y 0 ( y − y 0 ) + t 1 ∗ ( y 2 − y 1 )

可以看到 t1 的计算公式是一个叉积比例的形式,其实这个形式除了使用先前的解析方法,也可以运用几何方法来进行求解,只是对思维的要求比较高,有兴趣的朋友可以自己尝试一下(提示:叉积->面积).

有了 t1 和 t2 ,我们就可以计算之前的 V1’ , V2’ 和 t 了:

$\begin{aligned} V_1' & = (1 - t_2) * V_0 + t_2 * V_1 \\ V_2' & = (1 - t_2) * V_0 + t_2 * V_2 \\ t &= | \dfrac{t_1 * (P_2 - P_1)}{t_2 * (P_2 - P_1)} | = |\dfrac{t_1}{t_2}| \end{aligned}$ V 1 ′ V 2 ′ t = ( 1 − t 2 ) ∗ V 0 + t 2 ∗ V 1 = ( 1 − t 2 ) ∗ V 0 + t 2 ∗ V 2 = ∣ t 2 ∗ ( P 2 − P 1 ) t 1 ∗ ( P 2 − P 1 ) ∣ = ∣ t 2 t 1 ∣

方法对比

简单的测试对比发现,第二种插值方法较第一种 快 10% 左右 ~

Just My Type

Simon Garfield / Profile Books / 2010-10-21 / GBP 14.99

What's your type? Suddenly everyone's obsessed with fonts. Whether you're enraged by Ikea's Verdanagate, want to know what the Beach Boys have in common with easy Jet or why it's okay to like Comic Sa......一起来看看《Just My Type》这本书的介绍吧!

码农工具