algorithm - 在分段三次贝塞尔路径中插入点的算法

Question

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

有人知道贝塞尔算法的库或参考（插入、优化、de Casteljau ...）吗？

score 23 · Accepted Answer

这被称为“结插入问题”。对于贝塞尔曲线，de Casteljau 算法会给你正确的答案。这是 3 阶贝塞尔曲线的简单算法。

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

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.

几何解释很简单：在 fraction 处分割贝塞尔多边形的每一段t，然后将这些分割点连接到一个新的多边形中并进行迭代。当您剩下 1 个点时，该点位于曲线上，前一个/下一个分割点形成前一个/下一个贝塞尔多边形。同样的算法也适用于更高阶的贝塞尔曲线。

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

score 2 · Accepted Answer

您也可以采用数学方法。

带有控制点的 qubic Bézier 曲线 p_1,p_2,p_3,p_4 可以写成：

b(t)=(1-t)^3 p_1+3t(1-t)^2 p_2+3t^2 (1-t) p_3+t^3 p_4

它的导数是

$\frac{\partial b}{\partial t} = 3(1-t)^2 (p_2-p_1 )+6t(1-t)(p_3-p_2 )+3t^2 (p_4-p_3 )$

要将曲线从限制为，您将获得新的控制点 q_1,q_2,q_3,q_4 ：

q_1=b(t_0),q_4=b(t_1)

$q_2=q_1+\frac{1}{3}(t_1-t_0)\frac{\partial{b}}{\partial{t}}_{(t=t_0)}$

$q_3=q_4-\frac{1}{3}(t_1-t_0)\frac{\partial{b}}{\partial{t}}_{(t=t_1)}$

证明

替代

$s=\frac{t-t_0}{t_1-t_0}$

t=t_0+s(t_1-t_0 )

我们得到

$\frac{\partial b}{\partial s} = \frac{\partial b}{\partial t} \frac{\partial t}{\partial s} = (t_1-t_0) \frac{\partial b} {\部分时间}$

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

q_1=b(t_0),q_4=b(t_1)

这些点的切线是

$\frac{\partial{b}}{\partial{s}}_{(s=0)}=(t_1-t_0)\frac{\partial{b}}{\partial{t}}_{(t =t_0)}=3(q_2-q_1)$

$\frac{\partial{b}}{\partial{s}}_{(s=1)}=(t_1-t_0)\frac{\partial{b}}{\partial{t}}_{(t =t_1)}=3(q_4-q_3)$

所以

$q_2=q_1+\frac{1}{3}(t_1-t_0)\frac{\partial{b}}{\partial{t}}_{(t=t_0)}$

$q_3=q_4-\frac{1}{3}(t_1-t_0)\frac{\partial{b}}{\partial{t}}_{(t=t_1)}$

score 1 · Accepted Answer

添加这个是为了完整性。

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

algorithm - 在分段三次贝塞尔路径中插入点的算法

3 回答 3

证明

Related

Reference