计算立方贝塞尔长度的便宜方法

Question

立方贝塞尔长度的解析解似乎不存在,但这并不意味着不存在编码廉价解的编码.便宜我的意思是在50-100 ns(或更少)的范围内.

有人知道这样的事吗？可能分为两类:

1)较少的错误,如1%但更慢的代码.2)更多错误如20%但更快？

我通过谷歌扫描了一下,但它没有找到任何看起来像一个很好的解决方案.只有像划分N个线段并将N sqrt相加的东西 - 太慢以获得更高的精度,并且对于2或3个段可能太不准确.

有更好的吗？

Answer 1

另一种选择是将弧长估计为弦和控制网之间的平均值.在实践中:

Bezier bezier = Bezier (p0, p1, p2, p3);

chord = (p3-p0).Length;
cont_net = (p0 - p1).Length + (p2 - p1).Length + (p3 - p2).Length;

app_arc_length = (cont_net + chord) / 2;

然后,您可以递归地将样条线段分割为两个线段,并计算弧长直到收敛.我测试了自己,它实际上收敛得非常快.我从这个论坛得到了这个想法.

Answer 2

最简单的算法：拉平曲线并计算欧氏距离。只要你想要一个近似的弧长，这个解决方案既快速又便宜。给定曲线的坐标 LUT——你说的是速度，所以我假设你使用这些，而不是不断地重新计算坐标——这是一个带有计数的简单 for 循环。在通用代码中，使用dist计算两点之间的欧几里德距离的函数：

var arclength = 0,
    last=LUT.length-1,
    i;
for (i=0; i<last; i++) {
  arclength += dist(LUT[i], LUT[i+1]);
}

完毕。arclength现在是基于您可以在基于 LUT 的曲线中形成的最大段数的近似弧长。需要更大的潜在错误更快的事情？控制段数。

var arclength = 0,
    segCount = ...,
    last=LUT.length-2,
    step = last/segCount,
    s, i;
for (s=0; s<=segCount; s++) {
  i = (s*step/last)|0;
  arclength += dist(LUT[i], LUT[i+1]);
}

这几乎是最简单的算法，它仍然生成甚至接近真实弧长的值。为了更好，您将不得不使用更昂贵的数值方法（如勒让德-高斯正交技术）。

如果您想知道原因，请点击“贝塞尔曲线入门”的弧长部分。