Ask Your Question
1

how to get y component of bezier control points?

asked 2020-01-08 21:36:39 -0500

alienfetuseater gravatar image

or is there a utility in sage that returns the bezier control points of a curve given that curve?

im writing a program that takes a curve in polynomial form and returns those control points, this is the part in question:

def bezierControlPoints(poly):
    a = sage.var('a')
    b = sage.var('b')
    c = sage.var('c')
    d = sage.var('d')
    t = sage.var('t')
    bezier = ((1 - t) ** 3) * a + 3 * ((1 - t) ** 2) * t * \
        b + 3 * ((1 - t) * (t ** 2)) * c + (t ** 3) * d
    eqn1 = poly.substitute(t=0)
    eqn2 = poly.substitute(t=.33)
    eqn3 = poly.substitute(t=.66)
    eqn4 = poly.substitute(t=1)
    cb1 = bezier.substitute(t=0)
    cb2 = bezier.substitute(t=.33)
    cb3 = bezier.substitute(t=.66)
    cb4 = bezier.substitute(t=1)

    solns = sage.solve([eqn1 == cb1, eqn2 == cb2, eqn3 == cb3,
                        eqn4 == cb4], a, b, c, d, solution_dict=True)
    return [[s[a].n(30), s[b].n(30), s[c].n(30), s[d].n(30)] for s in solns]

but the control points are coordinates, and this returns single numbers like coefficients. for example

f(x) =  x^4 - 10*x^3 + 35*x^2 - 50*x + 24

returns

[24.000000, 3.8069265, -4.2949254, -0.30555556] 

[-0.30555556, 0.85185185, 0.85185185, -0.30555556] 

[-0.30555556, -1.3680046, -1.2661527, 0.00000000]

so how do i finish processing these portions of the control points?

background

the parts of the program i have written that i didnt share take the polynomial of arbitrary order, break it up into simpler subcurves, parameterize those subcurves, and those parameterized subcurves are the arguements of the bezierControlPoints(), which is called iteratively depending on the order of the polynomial.

edit retag flag offensive close merge delete

Comments

I am not sure about what you're trying to do (find control points knowing some function f), which is the reverse of the usual Bezier problem (find a polynomial knowing,the control points).

If I understand you correctly, you are looking for a "good" approximation of some function f (here a polynomial poly), by a cubic Bezier curve c. Such a curve has four "control points" P[0]..P[3].

Here, P(0] and P[3] are fully determined to be (0, f(0)) and (1, f(1)) respectively. Furthermore, the equality of slopes in 0 and 1 determine the slopes of P[0]-P[1] and P[2]-P[3].

You are left with only two unknowns, which are the abcissæ of P[1] and P[2]. to fix them, you must define the criteria of a "good" approximation of f by c, which should solve your problem.

Emmanuel Charpentier gravatar imageEmmanuel Charpentier ( 2020-01-09 05:02:19 -0500 )edit

@Emmanuel Charpentier: yes, this is the reverse of the typical bezier problem. what I am doing is taking hand drawn curves that I ultimately need rendered in a browser. this curves are polynomials of various order. So I am taking the curves parameterzing them, and the parameterized curves are then the argument for the above bezierControlPoints() method. i do realize that point P[0] = (0, poly(0)) and that point P[3] = (1, poly(1)). what the bezierControlPoints() method above does is set up a system of linear equations for various values of t, solving for the coefficients of the cubic bezier. and so my question is how do i take those results, those coefficients and convert them into coordinates of ordered pairs?

alienfetuseater gravatar imagealienfetuseater ( 2020-01-09 13:12:18 -0500 )edit

@Emmanuel Charpentier if i were to substitute those coefficients into poly i would just get some point along that curve, but the coefficients that i solve for with bezierControlPoints() are not the parameters of cubic bezier, that is what t is, so this is where my confusion lies

alienfetuseater gravatar imagealienfetuseater ( 2020-01-09 13:13:55 -0500 )edit
1

Okay, I see what you mean.

And my previous command is wrong: choose a change of scale and origin coaxing the problem on the intervl [0 1] and let f0 and f1 the values of the function at the extremities, d0 and d1 the derivatives at the same points. Then:

var("a, b, c, d, t", domain="real")
B(t)=a*t^3+b*t^2+c*t+d
dB(t)=diff(B(t),t)
var("f0,f1,d0,d1", domain="real")
Sol=solve([B(0)==f0, B(1)==f1, dB(0)==d0, dB(1)==d1],[a,b,c,d], solution_dict=True)
Sol
[{a: d0 + d1 + 2*f0 - 2*f1, b: -2*d0 - d1 - 3*f0 + 3*f1, c: d0, d: f0}]

Now, all that remains to do is to equate this to the canonical solution of Bezier curves. The difficulty is to find the "right" notation. Let me think ...(more)

Emmanuel Charpentier gravatar imageEmmanuel Charpentier ( 2020-01-09 15:10:38 -0500 )edit

1 answer

Sort by » oldest newest most voted
0

answered 2020-01-10 15:09:16 -0500

Emmanuel Charpentier gravatar image

Create a list of the control points:

LP=[vector([var("x_{}".format(u), domain="real"),
          var("y_{}".format(u),domain="real")])
      for u in (0..3)]
LP
[(x_0, y_0), (x_1, y_1), (x_2, y_2), (x_3, y_3)]

Utility function to express the Bernstein polynomials:

var("t")
Bn(p,j,t)=binomial(p,j)*t^j*(1-t)^(p-j)
Bn
(p, j, t) |--> t^j*(-t + 1)^(-j + p)*binomial(p, j)

We use it to get the parametric equation of the Bezier curve:

  Bz=sum(map(lambda u,v:u*v, [Bn(3,w,t) for w in (0..3)], LP))
  list(Bz)
[-(t - 1)^3*x_0 + 3*(t - 1)^2*t*x_1 - 3*(t - 1)*t^2*x_2 + t^3*x_3,
 -(t - 1)^3*y_0 + 3*(t - 1)^2*t*y_1 - 3*(t - 1)*t^2*y_2 + t^3*y_3]

and its derivative:

dBz=Bz.diff(t)
list(dBz)
(-3*(t - 1)^2*x_0 + 3*(t - 1)^2*x_1 + 6*(t - 1)*t*x_1 - 6*(t - 1)*t*x_2 - 3*t^2*x_2 + 3*t^2*x_3,
 -3*(t - 1)^2*y_0 + 3*(t - 1)^2*y_1 + 6*(t - 1)*t*y_1 - 6*(t - 1)*t*y_2 - 3*t^2*y_2 + 3*t^2*y_3)

Let d0 and d1 be the slopes of the function at begin and end points, and use them to define the equations constraining the equality of slopes:

var("d0, d1")
dB0=dBz(t=0)
E0=d0==dB0[1]/dB0[0]
dB1=dBz(t=1)
E1=d1==dB1[1]/dB1[0]
[E0,E1]
(d0, d1)
[d0 == (y_0 - y_1)/(x_0 - x_1), d1 == (y_2 - y_3)/(x_2 - x_3)]

These equations, along with the (implicit) equality of points (satisfied by keeping $(x_0, y_0)$ and $(x_3, y_3)$ as such), define the set of Bezier curves satisfying our constraints:

Sol=solve([E0, E1], [x_1, x_2, y_1, y_2])
print("len(Sol)={}".format(len(Sol)))
Sol[0]
len(Sol)=1
[x_1 == r8,
 x_2 == r7,
 y_1 == d0*r8 - d0*x_0 + y_0,
 y_2 == d1*r7 - d1*x_3 + y_3]

This means that any Bezier curve:

  • starting at $P_0=(x_0, y_0)$,

  • ending at $P_3=(x_3, y_3)$,

  • having $P_1$ somewhere on the line passing at $P_0$ with slope $d_0$, and

  • having $P_2$ somewhere on the line passing at $P_3$ with slope $d_1$

is a curve approximating (in some undefined sense) our original function and satisfying our constraints.

In fact, we have a double infinity of solutions. Choosing $x_1$ and $x_2$ can (should) therefore be done to satisfy further constraints, for example minimizing the mean square distance between the original function and the Bezier curve, and possibly other constraints (e. g. keeping the relation between $x$ and $t$ monotonic on $[x_0~x_3]\mapsto[0~1]$, i. e. no loop or cusp in the curve...).

One can also note that these Bezier curves cannot have a linear mapping of $t$ to $x$ (one can check that this implies $P_0=P_1=P_2$).

HTH,

edit flag offensive delete link more

Comments

thank you im studying your answer now

alienfetuseater gravatar imagealienfetuseater ( 2020-01-10 20:37:34 -0500 )edit

im trying to follow along with your code and im not sure where the input is supposed to be so i tried to read your code in english, let me express my understanding of what your suggesting and what im still confused by. so list an expression for the control points:

$LP = [(x_0,y_0),(x_1,y_1),(x_2,y_2),(x_3,y_3)]$.

with

LP=[vector([var("x_{}".format(u), domain="real"),
          var("y_{}".format(u),domain="real")])
      for u in (0..3)]

expression for bernstein basis polynomials:

$Bn(p,j,t) = {p\choose j}*t^j * (1-t)^{p-j}$, t = [0,1].

with

var("t")
Bn(p,j,t)=binomial(p,j)*t^j*(1-t)^(p-j)
alienfetuseater gravatar imagealienfetuseater ( 2020-01-15 08:43:22 -0500 )edit

expression for cubic bezier curve:

$Bz = \sum_{u=0}^{v} Bn(v,u,t) $ = ${(-(t - 1)^3x_0 + 3(t - 1)^2tx_1 - 3(t - 1)t^2x_2 + t^3x_3 ) $, $(-(t - 1)^3y_0 + 3(t - 1)^2ty_1 - 3(t - 1)t^2y_2 + t^3y_3) }$.

with

Bz=sum(map(lambda u,v:u*v, [Bn(3,w,t) for w in (0..3)], LP))

the expression for its derivatives:

$dBz = Bz'(t) = $

$ -3(t - 1)^2x_0 + 3(t - 1)^2x_1 + 6(t - 1)tx_1 - 6(t - 1)tx_2 - 3t^2x_2 + 3t^2x_3$, and $ -3(t - 1)^2y_0 + 3(t - 1)^2y_1 + 6(t - 1)ty_1 - 6(t - 1)ty_2 - 3t^2y_2 + 3t^2y_3$.

with

 dBz=Bz.diff(t)

you use these identities to create these equations:

$ dB_0 ...(more)

alienfetuseater gravatar imagealienfetuseater ( 2020-01-15 08:45:06 -0500 )edit

then you use sage to solve $E_0$ and $E_1$ for the control points with

Sol=solve([E0, E1], [x_1, x_2, y_1, y_2])

then Sol[0] returns:

[x_1 == r8,
 x_2 == r7,
 y_1 == d0*r8 - d0*x_0 + y_0,
 y_2 == d1*r7 - d1*x_3 + y_3]

so what are these r7 and r8 values? and where am i suppoosed to input the equation for my polynomial?

alienfetuseater gravatar imagealienfetuseater ( 2020-01-15 08:47:15 -0500 )edit

so what are these r7 and r8 values? and where am i suppoosed to input the equation for my polynomial?

Arbitrary (real) constants. See solve's documentation.

And, no, you are not supposed to input your polynomial. The equations define the constraints valid for any Bezier curve passing by thge end points with the "right" end slopes.

As I point out in the end, one cannot "solve" the parametric equations of a Bezier curve (x=f(t), y=g(t), f and g being third-degree polynomial) into a functional equation (y=h(x), with h polynomial) except in a very special degenerate case.

In plainer words, a cubic polynomial is not a Bezier curve...

Emmanuel Charpentier gravatar imageEmmanuel Charpentier ( 2020-01-15 11:34:23 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2020-01-08 21:36:39 -0500

Seen: 117 times

Last updated: Jan 10