Hello guys, I'm searching for algorithm such as : Line vs Bezier curve intersection test... And didn't find anything... Here is picture : So the normal depends on Line Segment direction, it will be pointed to line seg beginning, point A. So the normal is a unit vector like (0,1) or (0.5,0.5) it show as a perpendicular to intersection surface... I know that there can be many intersection points, but we pick that point which closer to point A of line segment... I'm not so smart in High mathematics, and cubical equations, and tangent equations, so help me please.. [Edited by - Lolmen on December 5, 2007 8:44:27 PM]

I'd start by getting everything relative to point A on the line. Then you can get an equation for your line something like mx+ny=0 where m = -By and n = Bx (that's B relative to A). Then you can substitute your bezier formulas (also relative to A)into the x and y in that equation, and get a new 1 dimensional cubic equation where the roots give the t values of the original bezier curve where it collides with that point. I'm not going to explain how to find the roots of a cubic equation because there's plenty of information online that explains it better than I could. Once you have the t values (there could be up to 3) you can substitute those back into your original bezier curve and check which point is the closest to A(that would be your M) . Once you have the closest t value you can put that into the derivative of your bezier curve to get the tangent vector at the point(T). There is a more complex definition of the normal to a curve, but it looks like you just want a normalized vector perpendicular to the curve facing a certain direction. So I'd suggest you use N=(-Ty,Tx) then if ( N.(A-M) <0) multiply N by -1, and of course finish up by dividing N by it's length.

P.S. The magnitude of (0.5,0.5) is sqrt(2)/2

I almost don't get anything, because As I say, High mathematic teh suck, and I can't clearly understand the concept.
Well I can undertand you, if you show it to me step by step with real samples, wow, forget one thing, for solve cubical equations in inet we can search for SolveCubic code... This can help us somehow...
But the rest part I strongly suggest show me how it works, like solve step by step without skipping some curve here, hence theorys without practical samples don't give me anything usable. :)

Somebody notice that best approx approach is react this intersection by using nishita Bezier clipping, but I don't find anything really good paper...

Thanks in advance...

[Edited by - Lolmen on December 3, 2007 12:35:49 PM]

I have found that paper using google.

Hah, that's exacly what I'm read before, but as I said, I'm not so smart in Mathematics... So if you can understand the concept, try to figure out some code...

I'm afraid I can't help in figuring out how to compute it, but I feel I should point out that an arbitrary line intersection with an arbitrary bezier COULD result in multiple intersections; two for a 3-point bezier (quadratic?) and three for a 4-point cubic bezier (twisted into a pretzel shape).

This may not be an issue for you if you know that your curves and lines fall within certain ranges where this won't happen.

I appreciate any working algorithm, to figure out how to be with multiple intersection pts we can just sorth them, to pick closest point to beginning of a line segment, so if you can help, try it.

The idea behind the algorithm presented in that paper is to define a new Bézier curve that represent the distance between the original Bézier curve and the line.

1. The first things to do is to write the equation of the line in implicit form. Given A(ax, ay), B(bx, by) and the vector d(dx, dy)=normalize(B-A) the equation is
dyx - dxy + C = 0
where C = aydx - axdy

2. The distance between a point and the line is defined by the following function:
dist(x,y) = dyx - dxy + C

2. The Bézier curve that describe the distance between the line and the points in the original Bézier curve is the following:
D(t) = (1-t)3dist(P0) + 3t(1-t)2dist(P1) + 3t2(1-t)dist(P2) + t3dist(P3)

3. You have at this point two possibilities: solve the cubic equation D(t) = 0 or use an approximated method like the one described in the paper. What method do you prefer?

P.S. I suggest to improve your math knowledge. You will probably find in the future harder problems to solve.

Edit:
The normal of a curve is traditionally described by the tangent vector rotated by 90°. But if you aren’t able to calculate the tangent vector it isn’t very useful. I’m currently unable to find a formula and I want to go to sleep.

[Edited by - apatriarca on December 3, 2007 5:22:06 PM]

I think pick method from this paper, if every body taliking about this Nishita'sh approach as first for real time graphics, so it should be faster than solve cubical equaton...

I understand the first thing...

But I'm not sure about thing №2...

[Edited by - Lolmen on December 5, 2007 8:59:51 PM]

What I have written is only math not code.
The first part of the equation of the line (dyx - dxy + C) is the formula (that I have called dist(x,y) in the 2) to find the distance between the line and the point (x, y). The points with the distance equals to zero are the points the lie on the line. The function described in 3 is a function that given the parameter t of a point on the Bézier curve returns it’s distance to the line.
How much do you know about Bézier curve?