在多个点分割一个三次贝塞尔曲线

Question

在多个点分割一个三次贝塞尔曲线

4

我正在编写一个算法，将立方贝塞尔曲线分割成多个曲线（最多4个）。我已经得到从开头开始每个点要拆分的t值。我还编写了一个用于一次分割曲线的算法：

SubdivPoints subdivideBezier(Vector2 p0, Vector2 p1, Vector2 p2, Vector2 p3, float t)
{
    Vector2 p11 = (p1 - p0) * t + p0;
    Vector2 p21 = (p2 - p1) * t + p1;
    Vector2 p31 = (p3 - p2) * t + p2;

    Vector2 p12 = (p21 - p11) * t + p11;
    Vector2 p22 = (p31 - p21) * t + p21;

    Vector2 p13 = (p22 - p12) * t + p12;

    return SubdivPoints(p11, p12, p22, p31, p13);
}

我的问题是，是否有一种简单的方法来扩展这个功能以进行多次分割？我想象每次分割后我都需要重新计算t值；我想知道的一件事是，简单的算术是否适用于此。例如，假设我有t值为0.2和0.6。我在t = 0.2处分割曲线，得到两条曲线。第二条曲线覆盖原始曲线中的0.2 < t < 1的t值。如果我通过除法重新计算第二个t值为0.6：(0.6-0.2) / (1-0.2) = 0.5，那么在t = 0.75处分割第二条曲线，这样行吗？或者我需要用其他方式重新计算它？

- jasonericson

2个回答

1

即使您当前的方法可行，也很难说其背后的SubdivPoints是什么。我可以想到两种方法：

algebraic

if you look at your problem as a parameter t scaling of polynomial then it became clearer. For example you want the control points for part t=<0.25,0.5>. That means we need form new control points representing the same curve with parameter u=<0.0,1.0>. How to do it?
1. write BEZIER as polynomial
each axis can be done separately in the same manner s lets us focus on x-axis only. We have 4 BEZIER control points with x-coordinates (x0,x1,x2,x3). If we apply bernstein polynoms to form cubic polynomial we get:
```
x(t)=      (                           (    x0))
    +    t*(                  (3.0*x1)-(3.0*x0))
    +  t*t*(         (3.0*x2)-(6.0*x1)+(3.0*x0))
    +t*t*t*((    x3)-(3.0*x2)+(3.0*x1)-(    x0))
```
1. rescale parameter by substitution
Use linear interpolation for that so:
```
t0=0.25 -> u0=0.0
t1=0.50 -> u1=1.0
t=t0+(t1-t0)*(u-u0)/(u1-u0)
t=0.25+0.5*u
```
now rewrite the polynomial using u instead of t
```
x(t)=             (                           (    x0))
    +(0.25+u/2)  *(                  (3.0*x1)-(3.0*x0))
    +(0.25+u/2)^2*(         (3.0*x2)-(6.0*x1)+(3.0*x0))
    +(0.25+u/2)^3*((    x3)-(3.0*x2)+(3.0*x1)-(    x0))
```
1. change the polynomial form to match BEZIER equation again
Now you need to separate terms of polynomial for u^0,u^1,u^2,u^3 and reform each to match BEZIER style (from #1). From that extract new control points.

For example term u^3 is like this. The only possibility of getting u^3 is from
```
(1/4+u/2)^3= (1/8)*u^3 + (3/16)*u^2 + (3/32)*u + (1/64)
```
so separated u^3 term will be:
```
u*u*u*((    x3)-(3.0*x2)+(3.0*x1)-(    x0))/8
```
the others will be a bit more complicated as you need combine all lines together ... After simplifying you will need to separate the new coordinates. As you can see it is slight madness but there are algebraic solvers out there like Derive for Windows ...

Sorry I do not have time/mood/stomach to make full example of all the terms but you will see it will be quite a polynomial madness...
curve fitting

this is based on that you are finding the coordinates of your control points and checking how far it is from your desired curve. So test ""all possible" points and remember the closes match between original curve on target range and new one. That would be insolvable as there is infinite number of control points possible so we need to cut down those to manageable size by exploiting something. For example we now the control points will not be to far from the original control points so we can use that to limit area for each point. You can use approximation search for this or any other minimization technique.

you can also get much much better start point for this if you use interpolation cubic. See BEZIER vs Interpolation cubics. So:
1. compute 4 new interpolation cubic control points from your BEZIER curve
  
  so if we have the same ranges as before then
```
X0 = BEZIER(t0-(t1-t0))
X1 = BEZIER(t0)
X2 = BEZIER(t1)
X3 = BEZIER(t1+(t1-t0))
```
  these are interpolation cubic control points not BEZIER. they should be uniformly dispersed. X1,X2 are the curve endpoints and X0,X3 are before and after them to preserve local shape and linearity of parameter as much as possible
2. transfrom (X0,X1,X2,X3) back into BEZIER control points (x0,x1,x2,x3)
  
  You can use mine formula from link above:
```
// input: X0,Y0,..X3,Y3  ... interpolation control points
// output: x0,y0,..x3,y3 ... Bezier control points
    double x0,y0,x1,y1,x2,y2,x3,y3,m=1.0/9.0;
    x0=X1;             y0=Y1;
    x1=X1+((X1-X0)*m); y1=Y1+((Y1-Y0)*m);
    x2=X2+((X2-X3)*m); y2=Y2+((Y2-Y3)*m);
    x3=X2;             y3=Y2;
```
  As you can see each axis is computed the same way ...
3. apply approximation search for BEZIER control points
  
  the new (x0,x1,x2,x3) are not precise yet as by changing control points blindly we could miss some local extreme of curve distorting shape slightly. So we need to search for the real ones. Luckily the new control points (x0',x1',x2',x3') will be very close to these points so now we have to search each point only near its counter part with some reasonable radius around (like bounding box size/8 or whatever ... you will see the results and can tweak ...

[笔记]

如果您需要精确的结果，则只能使用#1方法。方法#2总是会有一些误差。如果形状不需要完全精确，有时将插值立方体转换为BEZIER并省略最终拟合即可（如果形状在/靠近切割区域不太复杂）。

正如我之前所写的，如果不知道您的SubdivPoints使用的原理，就无法回答重复使用它的结果会是什么...

此外，您没有指定解决方案的约束条件，例如结果的精度、速度/运行时间限制...如果范围是固定的（常数），还是可以在运行时变化（这将极大地复杂化#1方法，因为您需要将范围处理为变量直到最后）。

- Spektre

SubdivPoints实际上只是这些点的结构体，它没有任何特殊作用。我稍后会使用这些点和控制点进行绘图，这是一个预处理步骤。因此，我有一组点和控制点来定义路径，并使用此步骤在某些位置（确切地说，在线条-曲线交点处）将其分割。然后它们在程序的其余部分中被固定。我感谢您详细的回答，但我希望能够扩展我已经使用的算法。这是不可能的吗？ - jasonericson

@jasonericson，你的subdivideBezier函数看起来就像是几何De Casteljau算法，只不过参数t被反转了。维基百科上说可以用它来进行分割，所以应该是可行的。同样地，Splitting a bezier curve也是以相同的方式使用它。因此，你可以尝试渲染/分割/渲染一些测试曲线，看看你所询问的算术是否真正有效，但我担心这不会很精确，因为t参数并不是从曲线开头开始的线性距离。 - Spektre

你的t边的线性组合仅在曲线的点密度恒定时才有效，这对于任意BEZIER曲线来说并不是常见情况。相反，你可以通过逼近搜索（只涉及1个变量）来找到第二条边缘t。 - Spektre

@jasonericson 计算原始曲线点 t=0.6，然后将其拆分为 t=<0.2,1.0> 并计算 around t=<0.75> 的点，在原始曲线点和拆分点之间的距离最小的情况下选择 t ... 然后使用该 t 进行第二次拆分... - Spektre

啊哈，非常感谢你提到的这个非常重要的点密度问题（虽然我无法用言语表达出来）。幸运/不幸的是，我在我的项目中已经不需要执行这个操作了，否则我会尝试你最后的建议。既然这个答案提供了很多有用的信息，我打算将其标记为正确答案。感谢你的帮助。 - jasonericson

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- fang · Accepted Answer

由于您的subdivideBezier()函数遵循了De Casteljau算法，我认为它可以在参数t处细分三次贝塞尔曲线。因此，是的，在不同的参数（比如t2）上继续细分，您需要做的就是找出t2所在的子曲线，计算该曲线上的新t2 *并进行细分。在您想要在t = 0.2和0.6处细分的示例中，0.6的新参数应为（0.6-0.2）/（1-0.2）= 0.5。因此，您只需在t = 0.5处细分第二条曲线即可。