Results 1 to 4 of 4

Math Help - Bezier curve evaluation

  1. #1
    Newbie
    Joined
    Jul 2007
    Posts
    2

    Bezier curve evaluation

    Hey!
    I'm currently working on a small vector graphics rasterizer to try out some different techniques. Basically, what I do is to take a spline outline consiting of straight lines and quadratic bezier curves, and fill that outline. I'm not satisfied with the performance and accuracy of my current scanline rasterizer...

    The new approach is more similar to how triangles in "regular 3d graphics" are rasterized. I evaluate if pixels lie within a triangle by using the edge functions of the three edges (implicit line ax + by + c) and checking the sign.

    But there are alot of bezier curves in the outline... It takes some time to convert the bezier curves into line segments (and then to proceed as described above).

    So my question is, is there any way to rewrite a bezier curve into something that resembles the edge function? I can't seem to figure it out quite...

    I've tried to rewrite a curve on the form ax + by + cx^2 + dx^2 + e (+ 0*xy) = 0, but it gets very messy, with roots and stuff which is not really cpu-friendly. I also tried converting the pixel coordinates to be evaluated into barycentric coordinates, but this also gets a bit messy, and I can't get rid of the divisions (two, one per coordinate)...

    I'm very thankful for any help, or even just a hint in any direction, because I fell a bit stuck. I really feel like I'm overlooking something, and this really shouldn't be too difficult :/

    I think I need a break and some coffee


    Thanks in advance!
    /Magnus
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Jul 2007
    Posts
    2
    Ok, perhaps I expressed myself in a too complicated way

    What I basically want to do is:
    For any given point, determine on which side of a quadratic bezier curve that point is.

    Secondarily I would like to know if it anyone knows if you can write a (all) quadratic bezier curve on the form, (and how to get it):

    Ax + By + Cx^2 + Dy^2 + E = 0

    I havn't found any info on the net regarding this :/

    Thanks!
    /Magnus
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Apr 2006
    Posts
    399
    Awards
    1
    Quote Originally Posted by repstosw View Post
    Hey!
    I'm currently working on a small vector graphics rasterizer to try out some different techniques. Basically, what I do is to take a spline outline consiting of straight lines and quadratic bezier curves, and fill that outline. I'm not satisfied with the performance and accuracy of my current scanline rasterizer...

    The new approach is more similar to how triangles in "regular 3d graphics" are rasterized. I evaluate if pixels lie within a triangle by using the edge functions of the three edges (implicit line ax + by + c) and checking the sign.

    But there are alot of bezier curves in the outline... It takes some time to convert the bezier curves into line segments (and then to proceed as described above).

    So my question is, is there any way to rewrite a bezier curve into something that resembles the edge function? I can't seem to figure it out quite...

    I've tried to rewrite a curve on the form ax + by + cx^2 + dx^2 + e (+ 0*xy) = 0, but it gets very messy, with roots and stuff which is not really cpu-friendly. I also tried converting the pixel coordinates to be evaluated into barycentric coordinates, but this also gets a bit messy, and I can't get rid of the divisions (two, one per coordinate)...

    I'm very thankful for any help, or even just a hint in any direction, because I fell a bit stuck. I really feel like I'm overlooking something, and this really shouldn't be too difficult :/

    I think I need a break and some coffee


    Thanks in advance!
    /Magnus
    Quote Originally Posted by repstosw View Post
    Ok, perhaps I expressed myself in a too complicated way

    What I basically want to do is:
    For any given point, determine on which side of a quadratic bezier curve that point is.

    Secondarily I would like to know if it anyone knows if you can write a (all) quadratic bezier curve on the form, (and how to get it):

    Ax + By + Cx^2 + Dy^2 + E = 0

    I havn't found any info on the net regarding this :/

    Thanks!
    /Magnus
    From Bezier curve - Wikipedia, the free encyclopedia, the parametric equation for a quadratic Bezier curve is



    From Parabola - Wikipedia, the free encyclopedia, the general equation for a parabola is



    and there are further conditions, including B^2 = 4AC.

    I don't know for a fact that a quadratic Bezier curve determines a parabola, but I'll assume it does. Given the condition on B, it cannot assumed that B = 0 as you indicate.

    Given the 3 points defining the Bezier curve, you want to determine the 6 coefficients of the parabola. Under the invertibility requirement below, you may set the coefficient F arbitrarily to a non-zero number, say F = -1. Then you need 5 linear equations to determine the other 5 unknown coefficients.

    Let (x_i,y_i) = \bold{B}(i/4),\ i = 0,\ldots, 4.

    Then the required 5 linear equations are

    \begin{bmatrix}<br />
  x_0^2 & x_0 y_0 & y_0^2 & x_0 & y_0 \\<br />
  x_1^2 & x_1 y_1 & y_1^2 & x_1 & y_1 \\<br />
  x_2^2 & x_2 y_2 & y_2^2 & x_2 & y_2 \\<br />
  x_3^2 & x_3 y_3 & y_3^2 & x_3 & y_3 \\<br />
  x_4^2 & x_4 y_4 & y_4^2 & x_4 & y_4   \end{bmatrix}<br />
  \begin{bmatrix} A \\ B \\ C \\ D \\ E \end{bmatrix} =<br />
  \begin{bmatrix} -F \\ -F \\ -F \\ -F \\ -F \end{bmatrix}.<br />

    To solve these equations requires that the matrix be invertible. That is the invertibility requirement that allows you to set F to an arbitrary non-zero number.

    There is a question whether the condition B^2 = 4AC will be satisfied. I think it must if the Bezier curve does indeed determine a parabola, which as I said I'm assuming is true.

    Once you have the coefficients, then which side of the Bezier curve a point (x,y) is on is determined by how the sign of G(x,y) = Ax^2 + Bxy + Cy^2 + Dx + Ey + F compares to the sign of G(\bar{x},\bar{y}) where (\bar{x},\bar{y}) = \bold{P_1}, the middle control point for the Bezier curve.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Apr 2006
    Posts
    399
    Awards
    1
    Quote Originally Posted by JakeD View Post
    From Bezier curve - Wikipedia, the free encyclopedia, the parametric equation for a quadratic Bezier curve is



    From Parabola - Wikipedia, the free encyclopedia, the general equation for a parabola is



    and there are further conditions, including B^2 = 4AC.

    I don't know for a fact that a quadratic Bezier curve determines a parabola, but I'll assume it does. Given the condition on B, it cannot assumed that B = 0 as you indicate.

    Given the 3 points defining the Bezier curve, you want to determine the 6 coefficients of the parabola. Under the invertibility requirement below, you may set the coefficient F arbitrarily to a non-zero number, say F = -1. Then you need 5 linear equations to determine the other 5 unknown coefficients.

    Let (x_i,y_i) = \bold{B}(i/4),\ i = 0,\ldots, 4.

    Then the required 5 linear equations are

    \begin{bmatrix}<br />
  x_0^2 & x_0 y_0 & y_0^2 & x_0 & y_0 \\<br />
  x_1^2 & x_1 y_1 & y_1^2 & x_1 & y_1 \\<br />
  x_2^2 & x_2 y_2 & y_2^2 & x_2 & y_2 \\<br />
  x_3^2 & x_3 y_3 & y_3^2 & x_3 & y_3 \\<br />
  x_4^2 & x_4 y_4 & y_4^2 & x_4 & y_4   \end{bmatrix}<br />
  \begin{bmatrix} A \\ B \\ C \\ D \\ E \end{bmatrix} =<br />
  \begin{bmatrix} -F \\ -F \\ -F \\ -F \\ -F \end{bmatrix}.<br />

    To solve these equations requires that the matrix be invertible. That is the invertibility requirement that allows you to set F to an arbitrary non-zero number.

    There is a question whether the condition B^2 = 4AC will be satisfied. I think it must if the Bezier curve does indeed determine a parabola, which as I said I'm assuming is true.

    Once you have the coefficients, then which side of the Bezier curve a point (x,y) is on is determined by how the sign of G(x,y) = Ax^2 + Bxy + Cy^2 + Dx + Ey + F compares to the sign of G(\bar{x},\bar{y}) where (\bar{x},\bar{y}) = \bold{P_1}, the middle control point for the Bezier curve.
    I wrote a program to test whether this method actually works. It typically does work: the Bezier curve typically does lie on the parabola with the given coefficients and the condition B^2 = 4AC is satisfied. But there is a catch.

    If for any t,\ \bold{B}(t) = (0,0), then the equation Ax^2 + Bxy + Cy^2 + Dx + Ey + F = 0 with (x,y) = (0,0) implies the coefficient F must equal 0 and cannot be set arbitrarily. If you do set F to a non-zero number and apply the method, you will get incorrect coefficients and the equation will perform badly around the point (x,y) = (0,0).

    But with F = 0, the equations

    \begin{bmatrix}<br />
  x_0^2 & x_0 y_0 & y_0^2 & x_0 & y_0 \\<br />
  x_1^2 & x_1 y_1 & y_1^2 & x_1 & y_1 \\<br />
  x_2^2 & x_2 y_2 & y_2^2 & x_2 & y_2 \\<br />
  x_3^2 & x_3 y_3 & y_3^2 & x_3 & y_3 \\<br />
  x_4^2 & x_4 y_4 & y_4^2 & x_4 & y_4   \end{bmatrix}<br />
  \begin{bmatrix} A \\ B \\ C \\ D \\ E \end{bmatrix} =<br />
  \begin{bmatrix} -F \\ -F \\ -F \\ -F \\ -F \end{bmatrix}.<br />

    would have only the trivial solution with all the coefficients equal to zero, which is not correct. There are now too many equations. So you could eliminate one and try solving

    \begin{bmatrix}<br />
  x_1^2 & x_1 y_1 & y_1^2 & x_1 & y_1 \\<br />
  x_2^2 & x_2 y_2 & y_2^2 & x_2 & y_2 \\<br />
  x_3^2 & x_3 y_3 & y_3^2 & x_3 & y_3 \\<br />
  x_4^2 & x_4 y_4 & y_4^2 & x_4 & y_4   \end{bmatrix}<br />
  \begin{bmatrix} A \\ B \\ C \\ D \\ E \end{bmatrix} =<br />
  \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \end{bmatrix}.<br />

    But those equations imply at least one of the coefficients may be set arbitrarily to a non-zero number. The trouble is, I don't think you can tell which coefficient that is. Whatever fixed choice you make, there may be some Bezier curve with a point \bold{B}(t) on the curve that makes that choice invalid. I don't see a solution to this.

    The bottom line is, to use this method, you must be sure that for all t \in [0,1],\ \bold{B}(t) \ne (0,0). Checking that involves solving two quadratic equations in t and verifying that the two solutions are different.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. it's a bezier problem.
    Posted in the Advanced Math Topics Forum
    Replies: 10
    Last Post: September 17th 2010, 04:38 AM
  2. Bezier Curves help?
    Posted in the Algebra Forum
    Replies: 0
    Last Post: August 23rd 2010, 11:04 PM
  3. Bezier curve derivative problem
    Posted in the Calculus Forum
    Replies: 0
    Last Post: February 27th 2010, 02:17 AM
  4. Replies: 0
    Last Post: April 6th 2009, 09:02 PM
  5. Cubic Bézier Curves
    Posted in the Advanced Applied Math Forum
    Replies: 0
    Last Post: June 15th 2008, 10:22 PM

Search Tags


/mathhelpforum @mathhelpforum