Started by Jul 29 2001 07:28 AM

,
7 replies to this topic

Posted 29 July 2001 - 07:28 AM

Hello!
I need help with a bezier curve (4 control points) and line intersection algorithm.
I have searched the web for such a function but without any luck :o(
If you already done this before or can point me in any direction, please drop me a msg!
/Peter - Thnx!

Posted 29 July 2001 - 04:23 PM

Are your line and bezier curve 2D or 3D? It makes a difference. And if 3D, do the bezier curve points lie in a plane? Again, it makes a big difference.

It seems possible that there may be a closed form solution for the 2D case. It would be ugly and would include some specialized techniques for algebraically or directly finding the roots of a polynomial of higher than order 2. Most likely, even in 2D, you''ll end up using an iterative method such as Newton''s method.

The 3D case would be very tricky indeed if the bezier curve points did not lie in a plane. Well, even if it does lie in a plane. Guaranteed you''d need to do it iteratively using Newton''s method or something related.

One intuitive way (and *robust* way) to solve your problem would be to discretize the bezier curve into a series of line segments and then see if the line intersects any of those line segments. It could be slower to do but would be easier to code, especially for the general 3D case.

Graham Rhodes

Senior Scientist

Applied Research Associates, Inc.

It seems possible that there may be a closed form solution for the 2D case. It would be ugly and would include some specialized techniques for algebraically or directly finding the roots of a polynomial of higher than order 2. Most likely, even in 2D, you''ll end up using an iterative method such as Newton''s method.

The 3D case would be very tricky indeed if the bezier curve points did not lie in a plane. Well, even if it does lie in a plane. Guaranteed you''d need to do it iteratively using Newton''s method or something related.

One intuitive way (and *robust* way) to solve your problem would be to discretize the bezier curve into a series of line segments and then see if the line intersects any of those line segments. It could be slower to do but would be easier to code, especially for the general 3D case.

Graham Rhodes

Senior Scientist

Applied Research Associates, Inc.

Posted 29 July 2001 - 11:00 PM

Hmmm...

p(t) = q(u)

(Let''s call the control points a,b,c,d and e,f,g,h)

a(1-t)^3 + 3bt(1-t)^2 + 3ct^2(1-t) + dt^3 = e(1-u)^3 + 3fu(1-u)^2 + 3gu^2(1-u) + hu^3

Now, observe that we have two unknowns (t and u), but only one equation, which is insufficient to figure out the values of t and u. So, it''s impossible to find the points of intersection using this method. If you could convert the parametric equations to cartesian equations (extremely difficult), then an algebraic method would follow easily (any volunteers?)

By far, the easiest method is to divide the curve up into line segments and test those for intersection - which really isn''t that slow unless you''re doing hundreds of tests per frame.

p(t) = q(u)

(Let''s call the control points a,b,c,d and e,f,g,h)

a(1-t)^3 + 3bt(1-t)^2 + 3ct^2(1-t) + dt^3 = e(1-u)^3 + 3fu(1-u)^2 + 3gu^2(1-u) + hu^3

Now, observe that we have two unknowns (t and u), but only one equation, which is insufficient to figure out the values of t and u. So, it''s impossible to find the points of intersection using this method. If you could convert the parametric equations to cartesian equations (extremely difficult), then an algebraic method would follow easily (any volunteers?)

By far, the easiest method is to divide the curve up into line segments and test those for intersection - which really isn''t that slow unless you''re doing hundreds of tests per frame.

Posted 30 July 2001 - 05:26 AM

quote:Original post by Beer Hunter

p(t) = q(u)

(Let''s call the control points a,b,c,d and e,f,g,h)

a(1-t)^3 + 3bt(1-t)^2 + 3ct^2(1-t) + dt^3 = e(1-u)^3 + 3fu(1-u)^2 + 3gu^2(1-u) + hu^3

Now, observe that we have two unknowns (t and u), but only one equation, which is insufficient to figure out the values of t and u. So, it''s impossible to find the points of intersection using this method.

ACTUALLY, you have *THREE* equations, . You have one *vector* equation, but actually 3 *scalar* equations, since p(t) and q(u) are both vector functions (assuming 3D line and bezier curve). And it is the number of scalar equations that is important.

Essentially in your one equation, the coefficients a, b, c, d, e, f, g, h are all 3-component vectors. So, say a is actually the vector (a_x, a_y, a_z), b is (b_x, b_y, b_z), etc. So that the coordinate p(t) = (p_x(t), p_y(t), p_z(t)) is found as:

p_x(t) = a_x(1-t)^3 + 3b_x*t(1-t)^2 + 3c_x*t^2(1-t) + d_x*t^3

p_y(t) = a_y(1-t)^3 + 3b_y*t(1-t)^2 + 3c_y*t^2(1-t) + d_y*t^3

p_z(t) = a_z(1-t)^3 + 3b_z*t(1-t)^2 + 3c_z*t^2(1-t) + d_z*t^3

Now you can expand your one vector equation to the following 3 scalar equations for x, y, and z components:

Equation (1):

a_x(1-t)^3 + 3b_x*t(1-t)^2 + 3c_x*t^2(1-t) + d_x*t^3 = e_x(1-u)^3 + 3f_x*u(1-u)^2 + 3g_x*u^2(1-u) + h_x*u^3

Equation (2):

a_y(1-t)^3 + 3b_y*t(1-t)^2 + 3c_y*t^2(1-t) + d_y*t^3 = e_y(1-u)^3 + 3f_y*u(1-u)^2 + 3g_y*u^2(1-u) + h_y*u^3

Equation (3):

a_z(1-t)^3 + 3b_z*t(1-t)^2 + 3c_z*t^2(1-t) + d_z*t^3 = e_z(1-u)^3 + 3f_z*u(1-u)^2 + 3g_z*u^2(1-u) + h_z*u^3

Now, here we are still using parametric equations (easier than cartesian I assure you), 2 unknowns (t and u) but 3 equations. That''s more than enough equations! And so this becomes a solveable problem. But still not an easy one. It is overdetermined and unless there is an exact intersection (unlikely in 3-space) the best you can do is something like a least squares solution to find the values of t and u that find the point where the curve and line come *closest* to touching. And the least squares solution is the true intersection when they are touching.

For 2D line and bezier curve you would have just my equations 1 and 2. Two equations and two unknowns and so you can find an exact solution if one exists.

Regarding conversion to cartesian-based equations, there simply is no appropriate way to represent *arbitrary* curves as functions of any cartesian coordinate [e.g.,, y = y(x) and z = z(x)] since an arbitrary curve might be multi-valued when projected into any given cartesian coordinate. If the curve loops completely there won''t be *any* cartesian direction that can work unless you split the curve into pieces.

I contributed a chapter to the upcoming "Game Programming Gems II" book from Charles River Media---coming out next month, and that chapter goes into complete detail on finding the intersection of 2 lines in 3-space. The detail in that chapter may help a bit with this problem, although once things get curvy, the math is just a mess.

After all this, I agree with Beer Hunter''s conclusion:

"By far, the easiest method is to divide the curve up into line segments and test those for intersection - which really isn''t that slow unless you''re doing hundreds of tests per frame."

Go this route and save yourself a nightmare.

Graham Rhodes

Senior Scientist

Applied Research Associates, Inc.

Posted 30 July 2001 - 10:43 AM

Thanx for your time!

Oboy, is this subject way to dificult for me or what. :o(

I will probably generate a lot of lines and do lineintersection tests instead.

Anyways... thanx!

/Peter

Oboy, is this subject way to dificult for me or what. :o(

I will probably generate a lot of lines and do lineintersection tests instead.

Anyways... thanx!

/Peter

Posted 30 July 2001 - 09:12 PM

I was worried that I might have missed something - thanks for pointing that out, grhodes.

Posted 01 August 2001 - 07:14 PM

How about you tessellate (or use the already tessellated patch from the renderer) and do line-triangle CD and approximate the point of intersection?

It's fairly important for performance reasons that you create a hierarchy of bounding volumes. You can use spheres, or boxes to enclose nested hierarchies of objects (i.e. a scene graph), to quickly determine if further CD needs to be performed.

P.S. If the object is free-moving in 3D, then it's a far more complicated problem - I think it's 7DoF; position +3DoF, orientation +3DoF, & time +1DoF. The method's I've read about suggest Runge-Kutta to iteratively solve the differential equations, with Brent's method thrown in to minimize when necessary.

Magmai Kai Holmlor

- Not For Rent

Ok after actually reading your post, I see you're using a curve and not a patch (I think I need due-diligence glasses), so instead of “tessellating” the patch, approximate the curve with line-segments, and do line-line CD.

Edited by - Magmai Kai Holmlor on August 2, 2001 2:16:45 AM

It's fairly important for performance reasons that you create a hierarchy of bounding volumes. You can use spheres, or boxes to enclose nested hierarchies of objects (i.e. a scene graph), to quickly determine if further CD needs to be performed.

P.S. If the object is free-moving in 3D, then it's a far more complicated problem - I think it's 7DoF; position +3DoF, orientation +3DoF, & time +1DoF. The method's I've read about suggest Runge-Kutta to iteratively solve the differential equations, with Brent's method thrown in to minimize when necessary.

Magmai Kai Holmlor

- Not For Rent

Ok after actually reading your post, I see you're using a curve and not a patch (I think I need due-diligence glasses), so instead of “tessellating” the patch, approximate the curve with line-segments, and do line-line CD.

Edited by - Magmai Kai Holmlor on August 2, 2001 2:16:45 AM

Posted 14 August 2001 - 03:34 AM

if the curve is 2d you can try to project it so that the ray is one of the axes and then to find the intersection just use quick search in a certian range ( test x values until the y sign is changed ) and project back to the original matrix .

that should do the work

the rubber-hound

that should do the work

the rubber-hound