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.

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.

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