在多个点处分割三次贝塞尔曲线 [英] Split a cubic bezier curve at multiple points

问题描述

我正在编写一种算法，它将三次三次贝塞尔曲线分成多条曲线(最多4条).我想从一开始就分配每个点的t值.我也已经有一种算法可以对曲线进行一次分割:

I'm writing an algorithm that will split a cubic bezier curve into multiple curves (up to 4). I have the t values for each point I want to split at from the beginning. I also have an algorithm already for splitting the curve once:

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处分割了曲线，给了我两条曲线.第二条曲线覆盖t值0.2≤t. t ＜ 1从原始.如果我通过除以(0.6-0.2)/(1- 0.2)= 0.5重新计算第二个t值0.6，然后将第二条曲线除以t = 0.75，这行得通吗?还是我需要以其他方式重新计算?

My question is, is there a simple way to expand this for splitting multiple times? I imagine after each split I want to recalculate the t values; one thing I'm wondering is if simple arithmetic will work here. E.g. Let's say I have t values 0.2 and 0.6. I split the curve at t = 0.2, giving me two curves. The second curve covers t values 0.2 < t < 1 from the original. If I recalculate the second t value of 0.6 by division: (0.6 - 0.2) / (1 - 0.2) = 0.5, then divide the second curve at t = 0.75, will that work? Or do I need to recalculate it some other way?

推荐答案

即使您当前的方法可行，也很难说，因为我们看不到SubdivPoints的含义.我可以想到两种方法:

very hard to say even if your current approach work as we do not see what is behind SubdivPoints. I can think of 2 approaches for this:

1. 代数

如果您将问题视为参数的多项式标度t缩放，那么它将变得更加清晰.例如，您希望零件t = <0.25,0.5>的控制点.这意味着我们需要形成新的控制点，这些控制点用参数u=<0.0,1.0>表示同一条曲线.怎么做?

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. 将BEZIER写为多项式

每个轴可以用相同的方式分别完成.s让我们仅关注x轴.我们有4个带有x坐标(x0,x1,x2,x3)的BEZIER控制点.如果我们将伯恩斯坦多项式应用于三次多项式，我们将得到:

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. 通过替换缩放参数

为此使用线性插值:

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

现在使用u而不是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. 更改多项式形式以再次匹配BEZIER方程

现在，您需要将u^0,u^1,u^2,u^3的多项式项分开，并分别进行重整以匹配BEZIER样式(来自#1 ).从中提取新的控制点.

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.

例如，术语u ^ 3就是这样.获取u ^ 3的唯一可能性是

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)

因此分开的u^3术语将是:

u*u*u*((    x3)-(3.0*x2)+(3.0*x1)-(    x0))/8

由于您需要将所有行组合在一起，其他的会更加复杂.简化之后，您将需要分离新的坐标.如您所见，这有点疯狂，但是那里有代数求解器，例如Windows的Derive ...

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...

曲线拟合

这是基于您正在寻找控制点的坐标，并检查其与所需曲线的距离是多少.因此，测试所有可能的"点，并记住目标范围上原始曲线与新曲线之间的闭合匹配，这是无法解决的，因为可能存在无限数量的控制点，因此我们需要通过利用某些东西将其减小到可控制的大小.例如，我们现在的控制点距离原始控制点不会太远，因此我们可以使用它来限制每个点的面积.您可以使用

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.

如果使用插值三次方，则可以获得更好的起点.请参阅 BEZIER与插值三次方.所以:

you can also get much much better start point for this if you use interpolation cubic. See BEZIER vs Interpolation cubics. So:

1. 从您的BEZIER曲线中计算4个新的插值三次控制点

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))

这些是插值三次控制点，而不是BEZIER.它们应均匀分散. X1,X2是曲线端点，X0,X3在曲线端点之前和之后，以尽可能保留参数的局部形状和线性

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

从(X0,X1,X2,X3)转换回BEZIER控制点(x0,x1,x2,x3)

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 ...

对BEZIER控制点应用近似搜索

apply approximation search for BEZIER control points

新的(x0,x1,x2,x3)尚不精确，因为通过盲目更改控制点，我们可能会略微忽略曲线变形的局部极限值.因此，我们需要搜索真实的.幸运的是，新的控制点(x0',x1',x2',x3')将非常靠近这些点，因此现在我们只需要在其对应部分附近以合理的半径搜索每个点(例如边界框size/8或其他...即可看到结果)并可以调整...

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 ...

[notes]

如果需要精确的精度结果，则仅使用#1 方法.方法#2 总是会有一些错误.如果形状不需要精确，有时将插值三次方转换为BEZIER，而无需最终拟合就足够了(如果形状在切面附近没有太复杂).

If you need the exact precision result then only the #1 approach is usable. Approach #2 will have always some error. If the shape does not need to be exact sometimes the interpolation cubic converted to BEZIER without the final fitting will suffice (if shape not too complex in/near cutted areas).

正如我之前写的那样，不知道您的SubdivPoints使用了哪个原理，不可能回答重复使用它会导致什么...

As I wrote before without knowing which principle is used in your SubdivPoints is impossible to answer what the result of repetitive use of it will be...

您还没有指定解决方案的约束，例如结果的准确性，速度/运行时限制...如果范围是固定的(恒定)或在运行时可以变化(这会使#1方法极端复杂化，因为您需要处理范围直到结束为止都是可变的

Also you did not specify the constrains of solution like accuracy of result, speed/runtime restrictions ... if the ranges are fixed (constant) or can vary during runtime (that will extremly complicate the #1 approach as you need to handle ranges as variable till the end)

这篇关于在多个点处分割三次贝塞尔曲线的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！