输入点不对齐的双线性插值法

Question

我有一组非网格对齐的输入值与网格对齐的输出值相关联。给定一个新的输入值，我想找到输出。

                                 

(这些是X,Y坐标，将一个不精确的非正方形眼球跟踪输入设备校准到屏幕上的精确位置。)

这看起来像 双线性插值但我的输入值并不是网格对齐的。在输入的情况下，我如何计算出一个合理的输出值？

---

答: 在这种情况下，当我有一组输入点和输出点时，实际需要的是执行 反双线插值 找到四边形中输入点的 U,V 坐标，然后使用这些 U,V 坐标对输出四边形进行法线插值（如下面 Nico 的回答中所述）。

Answer 1

你可以在任何凸四边形中进行双线插值。笛卡儿网格只是简单一点，因为插值参数的计算是琐碎的。在一般情况下，你的插值方法如下。

parameters alpha, beta
interpolated value = (1 - alpha) * ((1 - beta) * p1 + beta * p2) + alpha * ((1 - beta) * p3 + beta * p4)

为了计算参数，你必须解决一个方程系统。把你的输入值放在 p1 通过 p4 并求解 alpha 和 beta.

然后把你的输出值放在 p1 通过 p4 并使用计算出的参数来计算最终的插值。

对于常规的网格，参数计算的结果是。

alpha = x / cell width
beta  = y / cell height

这将自动解决方程。

下面是一个插值的示例 alpha=0.3 和 beta=0.6

其实，方程是可以分析解决的。但是，公式相当丑陋。因此，迭代法可能比较好。方程组有两种解法，你需要选择两个参数都在[0，1]的解。你需要选择两个参数都在[0，1]的解。

第一个解。

alpha = -(b e - a f + d g - c h + sqrt(-4 (c e - a g) (d f - b h) +
        (b e - a f + d g - c h)^2))/(2 c e - 2 a g)    
beta  = (b e - a f - d g + c h + sqrt(-4 (c e - a g) (d f - b h) + 
        (b e - a f + d g - c h)^2))/(2 c f - 2 b g)

其中

a = -p1.x + p3.x
b = -p1.x + p2.x
c = p1.x - p2.x - p3.x + p4.x
d = center.x - p1.x
e = -p1.y + p3.y
f = -p1.y + p2.y
g = p1.y - p2.y - p3.y + p4.y
h = center.y - p1.y

第二种解决方案。

alpha = (-b e + a f - d g + c h + sqrt(-4 (c e - a g) (d f - b h) + 
        (b e - a f + d g - c h)^2))/(2 c e - 2 a g)
beta  = -((-b e + a f + d g - c h + sqrt(-4 (c e - a g) (d f - b h) + 
        (b e - a f + d g - c h)^2))/( 2 c f - 2 b g))

Answer 2

这是我自己的技术，还有推导出结果值的代码。它需要三个 狼疮 的输出值（和三个百分比计算来确定 lerp 百分比）。

注意，这不是双线插值。 它并没有将输入点的四边形重映射到输出值的四边形，就如 一些输入点可能会导致输出值超出输出四边形。.

这里我显示的是笛卡尔平面上的非对齐输入值（使用上面问题中的样本输入值，为简单起见乘以10）。

                     

为了计算 "北 "点（顶部绿点），我们计算X轴上的百分比为

  (inputX - northwestX) / (northeastX - northwestX)
= (-4.2 - -19) / (10 - -19)
= 0.51034

我们用这个百分比来计算Y轴的截距，方法是在顶部Y值之间进行拉平。

  (targetValue - startValue) * percent + startValue
= (northeastY  - northwestY) * percent + northwestY
= (-8 - -7) * 0.51034 + -7
= -7.51034

我们在南边也做同样的工作。

  (inputX - southwestX) / (southeastX - southwestX)
= (-4.2 - -11) / (9 - -11)
= 0.34

  (southeastY - southwestY) * percent + southwestY
= (7 - 4) * 0.34 + 4
= 5.02

最后，我们用这两个值来计算南北边缘之间的最终百分比。

  (inputY - southY) / (northY - southY)
= (1 - 5.02) / (-7.51034 - 5.02)
= 0.3208

有了这三个百分比，我们就可以计算出最终的输出值 通过在点与点之间进行勒平运算

nw = Vector(-150,-100)
ne = Vector( 150,-100)
sw = Vector(-150, 100)
se = Vector( 150, 100)

north  = lerp( nw, ne, 0.51034)       --> (  3.10, -100.00)
south  = lerp( sw, se, 0.34)          --> (-48.00,  100.00)
result = lerp( south, north, 0.3208)  --> (-31.61,   35.84)

---

最后，这里是一些执行上述操作的（Lua）代码。它使用了一个可突变的Vector对象，该对象支持从另一个向量中复制值，并将其值向另一个向量进行勒平。

-- Creates a bilinear interpolator
-- Corners should be an object with nw/ne/sw/se keys,
-- each of which holds a pair of mutable Vectors
-- { nw={inp=vector1, out=vector2}, … }
function tetragonalBilinearInterpolator(corners)
  local sides = {
    n={ pt=Vector(), pts={corners.nw, corners.ne} },
    s={ pt=Vector(), pts={corners.sw, corners.se} }
  }

  for _,side in pairs(sides) do
    side.minX = side.pts[1].inp.x
    side.diff = side.pts[2].inp.x - side.minX
  end

  -- Mutates the input vector to hold the result
  return function(inpVector)
    for _,side in pairs(sides) do
      local pctX = (inpVector.x - side.minX) / side.diff
      side.pt:copyFrom(side.pts[1].inp):lerp(side.pts[2].inp,pctX)
      side.inpY = side.pt.y
      side.pt:copyFrom(side.pts[1].out):lerp(side.pts[2].out,pctX)
    end
    local pctY = (inpVector.y-sides.s.inpY)/(sides.n.y-sides.s.inpY)
    return inpVector:copyFrom(sides.s.pt):lerp(sides.n.pt,pctY)
  end
end

local interp = tetragonalBilinearInterpolator{
  nw={ inp=Vector(-19,-7),  out=Vector(-150,-100) },
  ne={ inp=Vector( 10,-8),  out=Vector( 150,-100) },
  sw={ inp=Vector(-11, 4),  out=Vector(-150, 100) },
  se={ inp=Vector(  9, 7),  out=Vector( 150, 100) }
}
print(interp(Vector(-4.2, 1))) --> <-31.60 35.84>