Intersection of bezier and straight line

Hi all,

I was wondering, how do we determine the a value 'Y' on a bezier when

you know the value of X coordinate.

ie. for X = (say) 10.0 , how do we find corrosponding Y value.

This problem reduces to finding intersection of line X=10 with the

given bezier.

Also I was wondering if it is possible to achive this using Dave

Eberly's Wild Magic library.

Thanks in Advance.

Regards

Yogesh

Re: Intersection of bezier and straight line

Hi,

I have two ideas, one is simple and stupid, the other is quite

complicated, but should be more efficient, let's see if there is

something interesting for you:

1. simple sampling

sample a Bezier curve by evaluating a parametric form of the Bezier

curve at equidistant discreet parameter values, check each sample if

it is close to x-value which are you lookign for, if necessary

adaptively increase the sampling rate, also note that there can be

several values of Y for one X

2. Bezier clipping

unfortunatelly I don't have any references here, but if you google

"Bezier clipping" you will find something for sure, it is a recursive

numerical approach which uses some nice properties of Bezier curves

(variation dimnishing property, convex hull) and it is said to be

quite stable, it has been used in the area of raytracing Bezier

patches quite extensively

jindra

On May 18, 3:30 pm, yogesh.k...@gmail.com wrote:

> Hi all,

> I was wondering, how do we determine the a value 'Y' on a bezier when

> you know the value of X coordinate.

> ie. for X = (say) 10.0 , how do we find corrosponding Y value.

> This problem reduces to finding intersection of line X=10 with the

> given bezier.

>

> Also I was wondering if it is possible to achive this using Dave

> Eberly's Wild Magic library.

>

> Thanks in Advance.

> Regards

> Yogesh

Re: Intersection of bezier and straight line

jindra wrote:

> I have two ideas, one is simple and stupid, the other is quite

> complicated, but should be more efficient, let's see if there is

> something interesting for you:

> 1. simple sampling

> sample a Bezier curve by evaluating a parametric form of the Bezier

> curve at equidistant discreet parameter values, check each sample if

> it is close to x-value which are you lookign for, if necessary

> adaptively increase the sampling rate, also note that there can be

> several values of Y for one X

This is basically a generic naive root-finding algorithm. There are

plenty of _good_ generic root-finding algorithms that one can find with

a little bit of searching, which will be a lot faster and not much more

complex. :)

For that matter, for a given spline segment X is cubic in T, and cubic

polynomials can be inverted directly, so there's no need for an

iterative method anyway. So you solve for T, and then plug that into

the equation for Y.

- Brooks

--

The "bmoses-nospam" address is valid; no unmunging needed.

Re: Intersection of bezier and straight line

> I was wondering, how do we determine the a value 'Y' on a bezier when

> you know the value of X coordinate.

Solve roots t for polynomial x(t) = given x. Closed form solution for

quadratic or cubic Beziers.

Plug t's into y(t).

Mind the degenerate cases. You can have 1, 2, 3 or infinite solutions.

Re: Intersection of bezier and straight line

<yogesh.kini@gmail.com> wrote in message

news:1179495050.245414.248160@h2g2000hsg.googlegroups.com...

> I was wondering, how do we determine the a value 'Y' on a bezier when

> you know the value of X coordinate.

> ie. for X = (say) 10.0 , how do we find corrosponding Y value.

> This problem reduces to finding intersection of line X=10 with the

> given bezier.

If the curve is (x(t),y(t)) and the vertical line is x = x0, you need

to compute the roots to the polynomial p(t) = x(t) - x0. For each

root T, compute the y-value y(T).

As mentioned by another poster, if the curve is degree 3, then you

could use the closed-form equations for the roots to a cubic. Be

aware, though, that those equations are notoriously ill-conditioned

when you have two roots that are nearly the same.

> Also I was wondering if it is possible to achive this using Dave

> Eberly's Wild Magic library.

By example:

int Generic::Main (int, char**)

{

// The Bezier curve is

// (x(t),y(t)) = (1-t)^3*P0 + 3*(1-t)^2*t*P1 + 3*(1-t)*t^2*P2 + t^3*P3

// for 0 <= t <= 1.

const int iDegree = 3;

Vector2d* akCtrlPoint = WM4_NEW Vector2d[iDegree + 1];

akCtrlPoint[0] = Vector2d( 0.0,0.0);

akCtrlPoint[1] = Vector2d( 3.0,1.0);

akCtrlPoint[2] = Vector2d(-1.0,2.0);

akCtrlPoint[3] = Vector2d( 4.0,4.0);

BezierCurve2d kCurve(iDegree, akCtrlPoint);

// The polynomial x(t).

Polynomial1d kXPoly(iDegree);

kXPoly[0] = kCurve.GetPosition(0.0)[0];

kXPoly[1] = kCurve.GetFirstDerivative(0.0)[0];

kXPoly[2] = kCurve.GetSecondDerivative(0.0)[0]/2.0;

kXPoly[3] = kCurve.GetThirdDerivative(0.0)[0]/6.0;

// The vertical line x = x0.

double dX0 = 1.26;

// Solve for x(t) = x0.

kXPoly[0] -= dX0;

int iDigits = 8;

PolynomialRootsd kPR(Mathd::ZERO_TOLERANCE);

kPR.FindB(kXPoly,iDigits);

// I have chosen the curve and an x0 so that the vertical line

// intersects the curve 3 times.

int iCount = kPR.GetCount();

const double* adRoot = kPR.GetRoots();

// root[0] = 0.33563439076802315

// root[1] = 0.42569287040671300

// root[2] = 0.55117273179554338

double dY0 = kCurve.GetPosition(adRoot[0])[1];

double dY1 = kCurve.GetPosition(adRoot[1])[1];

double dY2 = kCurve.GetPosition(adRoot[2])[1];

// y0 = 1.0447125355351101

// y1 = 1.3542202977928879

// y2 = 1.8209597203487196

return 0;

}

--

Dave Eberly

http://www.geometrictools.com

Re: Intersection of bezier and straight line

Hi all,

Thanks for all the replies.

Also Many Many Thanks to Dave for creating such a great open source

library(Wild Magic).

Wild Magic is truely awesome and seems to have all the math you will

ever need :-)

Best Regards

Yogesh

Re: Intersection of bezier and straight line

On May 19, 12:02 pm, "Dave Eberly" <dNOSPAMebe...@usemydomain.com>

wrote:

> <yogesh.k...@gmail.com> wrote in message

>

> news:1179495050.245414.248160@h2g2000hsg.googlegroups.com...

>

> > I was wondering, how do we determine the a value 'Y' on a bezier when

> > you know the value of X coordinate.

> > ie. for X = (say) 10.0 , how do we find corrosponding Y value.

> > This problem reduces to finding intersection of line X=10 with the

> > given bezier.

>

> If the curve is (x(t),y(t)) and the vertical line is x = x0, you need

> to compute the roots to the polynomial p(t) = x(t) - x0. For each

> root T, compute the y-value y(T).

>

> As mentioned by another poster, if the curve is degree 3, then you

> could use the closed-form equations for the roots to a cubic. Be

> aware, though, that those equations are notoriously ill-conditioned

> when you have two roots that are nearly the same.

>

> > Also I was wondering if it is possible to achive this using Dave

> > Eberly's Wild Magic library.

>

> By example:

>

> int Generic::Main (int, char**)

> {

> // The Bezier curve is

> // (x(t),y(t)) = (1-t)^3*P0 + 3*(1-t)^2*t*P1 + 3*(1-t)*t^2*P2 + t^3*P3

> // for 0 <= t <= 1.

> const int iDegree = 3;

> Vector2d* akCtrlPoint = WM4_NEW Vector2d[iDegree + 1];

> akCtrlPoint[0] = Vector2d( 0.0,0.0);

> akCtrlPoint[1] = Vector2d( 3.0,1.0);

> akCtrlPoint[2] = Vector2d(-1.0,2.0);

> akCtrlPoint[3] = Vector2d( 4.0,4.0);

> BezierCurve2d kCurve(iDegree, akCtrlPoint);

>

> // The polynomial x(t).

> Polynomial1d kXPoly(iDegree);

> kXPoly[0] = kCurve.GetPosition(0.0)[0];

> kXPoly[1] = kCurve.GetFirstDerivative(0.0)[0];

> kXPoly[2] = kCurve.GetSecondDerivative(0.0)[0]/2.0;

> kXPoly[3] = kCurve.GetThirdDerivative(0.0)[0]/6.0;

>

> // The vertical line x = x0.

> double dX0 = 1.26;

>

> // Solve for x(t) = x0.

> kXPoly[0] -= dX0;

> int iDigits = 8;

> PolynomialRootsd kPR(Mathd::ZERO_TOLERANCE);

> kPR.FindB(kXPoly,iDigits);

>

> // I have chosen the curve and an x0 so that the vertical line

> // intersects the curve 3 times.

> int iCount = kPR.GetCount();

> const double* adRoot = kPR.GetRoots();

> // root[0] = 0.33563439076802315

> // root[1] = 0.42569287040671300

> // root[2] = 0.55117273179554338

>

> double dY0 = kCurve.GetPosition(adRoot[0])[1];

> double dY1 = kCurve.GetPosition(adRoot[1])[1];

> double dY2 = kCurve.GetPosition(adRoot[2])[1];

> // y0 = 1.0447125355351101

> // y1 = 1.3542202977928879

> // y2 = 1.8209597203487196

>

> return 0;

>

> }

>

> --

> Dave Eberlyhttp://www.geometrictools.com

Hi Dave,

Am very very impressed by looking at this post.I am very much

intersted in the way you would actually be finding the intersection

points of a bezier and a straight line.I would love to know how the

polynomial equation is created using the bezier contol points and then

how are the roots actually calculated using the 1st,2nd and third

derivatives of the polynomial.Could you give me a little insight into

this

Thanks and Regards

Praveen

Re: Intersection of bezier and straight line

<praveenk.dj@gmail.com> wrote in message

news:1179724518.618315.58170@z28g2000prd.googlegroups.com...

> I am very much intersted in the way you would actually be finding

> the intersection points of a bezier and a straight line.

The source code I posted is the way I find the intersection

points of a Bézier curve and a vertical line, so I do not understand

your statement. Are you interested instead to compute the

intersection of the curve with an arbitrary line?

> I would love to know how the polynomial equation is created

> using the bezier contol points and then how are the roots

> actually calculated using the 1st,2nd and third derivatives

> of the polynomial.

The Bézier curve I mentioned is

P(t) = (1-t)^3*P0 + 3*(1-t)^2*t*P1 + 3*(1-t)*t^2*P2 + t^3*P3

where P0, P1, P2, and P3 are the user-specified control points, and

where 0 <= t <= 1. In standard form, the polynomial is

P(t) = C0 + t*C1 + t^2*C2 + t^3*C3

The first three derivatives are

P'(t) = C1 + 2*t*C2 + 3*t^2*C3

P''(t) = 2*C2 + 6*t*C3

P'''(t) = 6*C3

Notice that C0 = P(0), C1 = P'(0), C2 = P''(0)/2, and C3 = P'''(0)/6,

which is what I computed in the sample code.

Equivalently, I could have expanded the Bézier form for P(t) as

P(t) = P0 + t*(-3*P0+3*P1) + t^2*(3*P0-6*P1+3*P2)

+ t^3*(-P0+3*P1-3*P2+P3)

to obtain C0, C1, C2, and C3.

--

Dave Eberly

http://www.geometrictools.com

Re: Intersection of bezier and straight line

On May 21, 10:59 am, "Dave Eberly" <dNOSPAMebe...@usemydomain.com>

wrote:

> <praveenk...@gmail.com> wrote in message

>

> news:1179724518.618315.58170@z28g2000prd.googlegroups.com...

>

> > I am very much intersted in the way you would actually be finding

> > the intersection points of a bezier and a straight line.

>

> The source code I posted is the way I find the intersection

> points of a Bézier curve and a vertical line, so I do not understand

> your statement. Are you interested instead to compute the

> intersection of the curve with an arbitrary line?

>

> > I would love to know how the polynomial equation is created

> > using the bezier contol points and then how are the roots

> > actually calculated using the 1st,2nd and third derivatives

> > of the polynomial.

>

> The Bézier curve I mentioned is

> P(t) = (1-t)^3*P0 + 3*(1-t)^2*t*P1 + 3*(1-t)*t^2*P2 + t^3*P3

> where P0, P1, P2, and P3 are the user-specified control points, and

> where 0 <= t <= 1. In standard form, the polynomial is

> P(t) = C0 + t*C1 + t^2*C2 + t^3*C3

> The first three derivatives are

> P'(t) = C1 + 2*t*C2 + 3*t^2*C3

> P''(t) = 2*C2 + 6*t*C3

> P'''(t) = 6*C3

> Notice that C0 = P(0), C1 = P'(0), C2 = P''(0)/2, and C3 = P'''(0)/6,

> which is what I computed in the sample code.

>

> Equivalently, I could have expanded the Bézier form for P(t) as

> P(t) = P0 + t*(-3*P0+3*P1) + t^2*(3*P0-6*P1+3*P2)

> + t^3*(-P0+3*P1-3*P2+P3)

> to obtain C0, C1, C2, and C3.

>

> --

> Dave Eberlyhttp://www.geometrictools.com

Hi Dave,

Thanks for explaining the way u have calculated the coefficients using

the derivatives.I am very new to cubic curves and it was really

helpful.

Thanks and Regards

Praveen

Thanks and Regards

Praveen

Re: Intersection of bezier and straight line

On May 21, 10:59 am, "Dave Eberly" <dNOSPAMebe...@usemydomain.com>

wrote:

> <praveenk...@gmail.com> wrote in message

>

> news:1179724518.618315.58170@z28g2000prd.googlegroups.com...

>

> > I am very much intersted in the way you would actually be finding

> > the intersection points of a bezier and a straight line.

>

> The source code I posted is the way I find the intersection

> points of a Bézier curve and a vertical line, so I do not understand

> your statement. Are you interested instead to compute the

> intersection of the curve with an arbitrary line?

>

> > I would love to know how the polynomial equation is created

> > using the bezier contol points and then how are the roots

> > actually calculated using the 1st,2nd and third derivatives

> > of the polynomial.

>

> The Bézier curve I mentioned is

> P(t) = (1-t)^3*P0 + 3*(1-t)^2*t*P1 + 3*(1-t)*t^2*P2 + t^3*P3

> where P0, P1, P2, and P3 are the user-specified control points, and

> where 0 <= t <= 1. In standard form, the polynomial is

> P(t) = C0 + t*C1 + t^2*C2 + t^3*C3

> The first three derivatives are

> P'(t) = C1 + 2*t*C2 + 3*t^2*C3

> P''(t) = 2*C2 + 6*t*C3

> P'''(t) = 6*C3

> Notice that C0 = P(0), C1 = P'(0), C2 = P''(0)/2, and C3 = P'''(0)/6,

> which is what I computed in the sample code.

>

> Equivalently, I could have expanded the Bézier form for P(t) as

> P(t) = P0 + t*(-3*P0+3*P1) + t^2*(3*P0-6*P1+3*P2)

> + t^3*(-P0+3*P1-3*P2+P3)

> to obtain C0, C1, C2, and C3.

>

> --

> Dave Eberlyhttp://www.geometrictools.com

Hi Dave,

Yes,I am actually interested to know how the intersection points of a

cubic curve with any generic straight line is calculated.Could you

please explain me that as well

Thanks and Regards

Praveen