分段三次Bézier路径上的插点算法

Question

我正在寻找一种算法，在贝塞尔曲线上插入一个新的控制点，而不变形。

有谁知道贝塞尔算法的库或参考资料(插入、优化、de Casteljau ...)？

Answer 1

这被称为“节点插入问题”。对于Bézier曲线，de Casteljau算法将给出正确的答案。这是3次贝塞尔曲线的简单算法。

假设您想要在P0, P1, P2, P3定义的贝塞尔曲线内参数空间的分数t处插入一个结。下面是你要做的：

P0_1 = (1-t)*P0 + t*P1
P1_2 = (1-t)*P1 + t*P2
P2_3 = (1-t)*P2 + t*P3

P01_12 = (1-t)*P0_1 + t*P1_2
P12_23 = (1-t)*P1_2 + t*P2_3

P0112_1223 = (1-t)*P01_12 + t*P12_23

然后，您的第一个贝塞尔曲线将由：P_0, P0_1, P01_12, P0112_1223定义；第二个贝塞尔曲线将由：P0112_1223, P12_23, P2_3, P3定义。

几何解释很简单:以分数t分割Bézier多边形的每一段，然后将这些分割点连接到一个新多边形中并迭代。当剩下1个点时，该点位于曲线上，上一个/下一个分割点形成上一个/下一个贝塞尔多边形。同样的算法也适用于高次Bézier曲线。

现在，如果您希望在空间中的特定位置而不是在t的特定值处插入控制点，则可能会变得更加棘手。就我个人而言，我在这里所做的只是一个简单的二进制搜索，寻找一个接近所需分割点的t值……但如果性能很关键，您可能会找到一个更快的分析解决方案。

Answer 2

你也可以采用数学方法。

带控制点的二次Bézier曲线

可以写成：

​

​

它的导数w.r.t.

是

​

​

从以下位置限制曲线

至

，您将获得新的控制点

​

​

​

​

​

​

证明

替换

​

​

​

​

我们会得到

​

​

子曲线的第一个和最后一个点是第一个和最后一个新控制点。

​

​

在这些点上的切线是

​

​

​

​

所以

​

​

​

​

Answer 3

添加这个是为了完整性。

在gimpbezierstroke.c的GIMP源代码中可以找到许多贝塞尔曲线路径操作的开源实现。有关插入新锚点的参考信息，请搜索gimp_bezier_stroke_anchor_insert。