Intersection of bezier and straight line
yoges...@gmail.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.
Also I was wondering if it is possible to achive this using Dave
Eberly's Wild Magic library.
Thanks in Advance.
Regards
Yogesh
jindra
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
Brooks Moses
> 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.
Richard J Kinch
> 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.
Dave Eberly
news:1179495050.2...@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
yoges...@gmail.com
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
prave...@gmail.com
wrote:
> <yogesh.k...@gmail.com> wrote in message
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
Dave Eberly
news:1179724518....@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.
prave...@gmail.com
wrote:
> <praveenk...@gmail.com> wrote in message
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
prave...@gmail.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
jindra
if the cubic curve is affine invariant (as for example Bezier curves),
rotate a control polygon so that a generic line is horizontal/
vertical, use Dave's solution and rotate back
jindra
Dave Eberly
news:1179732301....@36g2000prm.googlegroups.com...
> Yes,I am actually interested to know how the intersection points
> of a cubic curve with any generic straight line is calculated.
The Bézier curve is P(t). The line is parameterized by L(s) = Q + s*D,
where Q is a point on the line and D is a unit-length direction vector.
You want to know at which t and s the curve and line intersect, so
you need to solve P(t) = L(s). Dot this equation with a vector
perpendicular to D. If D = (d1,d2), choose Perp(D) = (d2,-d1). Then
0 = Dot(Perp(D),P(t) - Q)
is a polynomial in t. Compute its roots. For each root T, the
intersection point is P(T). If you need the line parameter, dot the
equation with D to obtain s = Dot(D,P(T)-Q).
Here is the modified source code that computes the intersection of
the Bézier curve with a line that is not vertical, but slightly rotated
from the vertical line.
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);
Vector2d kC0 = kCurve.GetPosition(0.0);
Vector2d kC1 = kCurve.GetFirstDerivative(0.0);
Vector2d kC2 = kCurve.GetSecondDerivative(0.0)/2.0;
Vector2d kC3 = kCurve.GetThirdDerivative(0.0)/6.0;
// The polynomial x(t).
Polynomial1d kXPoly(iDegree);
kXPoly[0] = kC0[0];
kXPoly[1] = kC1[0];
kXPoly[2] = kC2[0];
kXPoly[3] = kC3[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
// Rather than a vertical line, rotate the line slightly and compute
// the intersections with the Bezier curve.
Line2d kLine;
kLine.Origin = Vector2d(dX0,0.0);
kLine.Direction = Vector2d(0.001,1.0);
kLine.Direction.Normalize();
Vector2d kDelta = kC0 - kLine.Origin;
Vector2d kPerp = kLine.Direction.Perp();
Polynomial1d kPoly(iDegree);
kPoly[0] = kPerp.Dot(kDelta);
kPoly[1] = kPerp.Dot(kC1);
kPoly[2] = kPerp.Dot(kC2);
kPoly[3] = kPerp.Dot(kC3);
kPR.FindB(kPoly,iDigits);
iCount = kPR.GetCount();
adRoot = kPR.GetRoots();
// root[0] = 0.33923911604965618
// root[1] = 0.41813347162768660
// root[2] = 0.55520944953684748
Vector2d kIntersect0 = kCurve.GetPosition(adRoot[0]);
Vector2d kIntersect1 = kCurve.GetPosition(adRoot[1]);
Vector2d kIntersect2 = kCurve.GetPosition(adRoot[2]);
// I0 = (1.2610567580636776, 1.0567580636775757)
// I1 = (1.2613275050313155, 1.3275050313155945)
// I2 = (1.2618367758437448, 1.8367758437447035)
return 0;
prave...@gmail.com
wrote:
> <praveenk...@gmail.com> wrote in message
Hi all,
Thanks for being so helpful
Regards
Praveen