Bezier curve evaluation

**repstosw** · July 30th 2007, 05:05 AM

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

**repstosw** · July 31st 2007, 12:52 AM

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

**JakeD** · August 1st 2007, 09:16 PM

Originally Posted by repstosw

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

Originally Posted by repstosw

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} x_0^2 & x_0 y_0 & y_0^2 & x_0 & y_0 \\ x_1^2 & x_1 y_1 & y_1^2 & x_1 & y_1 \\ x_2^2 & x_2 y_2 & y_2^2 & x_2 & y_2 \\ x_3^2 & x_3 y_3 & y_3^2 & x_3 & y_3 \\ x_4^2 & x_4 y_4 & y_4^2 & x_4 & y_4 \end{bmatrix} \begin{bmatrix} A \\ B \\ C \\ D \\ E \end{bmatrix} = \begin{bmatrix} -F \\ -F \\ -F \\ -F \\ -F \end{bmatrix}. $

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.

**JakeD** · August 4th 2007, 02:00 AM

Originally Posted by JakeD

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} x_0^2 & x_0 y_0 & y_0^2 & x_0 & y_0 \\ x_1^2 & x_1 y_1 & y_1^2 & x_1 & y_1 \\ x_2^2 & x_2 y_2 & y_2^2 & x_2 & y_2 \\ x_3^2 & x_3 y_3 & y_3^2 & x_3 & y_3 \\ x_4^2 & x_4 y_4 & y_4^2 & x_4 & y_4 \end{bmatrix} \begin{bmatrix} A \\ B \\ C \\ D \\ E \end{bmatrix} = \begin{bmatrix} -F \\ -F \\ -F \\ -F \\ -F \end{bmatrix}. $

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} x_0^2 & x_0 y_0 & y_0^2 & x_0 & y_0 \\ x_1^2 & x_1 y_1 & y_1^2 & x_1 & y_1 \\ x_2^2 & x_2 y_2 & y_2^2 & x_2 & y_2 \\ x_3^2 & x_3 y_3 & y_3^2 & x_3 & y_3 \\ x_4^2 & x_4 y_4 & y_4^2 & x_4 & y_4 \end{bmatrix} \begin{bmatrix} A \\ B \\ C \\ D \\ E \end{bmatrix} = \begin{bmatrix} -F \\ -F \\ -F \\ -F \\ -F \end{bmatrix}. $

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} x_1^2 & x_1 y_1 & y_1^2 & x_1 & y_1 \\ x_2^2 & x_2 y_2 & y_2^2 & x_2 & y_2 \\ x_3^2 & x_3 y_3 & y_3^2 & x_3 & y_3 \\ x_4^2 & x_4 y_4 & y_4^2 & x_4 & y_4 \end{bmatrix} \begin{bmatrix} A \\ B \\ C \\ D \\ E \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \end{bmatrix}. $

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.

Thread: Bezier curve evaluation

LinkBack

Thread Tools

Display

Bezier curve evaluation

Similar Math Help Forum Discussions

it's a bezier problem.

Bezier Curves help?

Bezier curve derivative problem

About drawing bezier curve without control points.

Cubic Bézier Curves

Search Tags