Archived

This topic is now archived and is closed to further replies.

JOL

Bezier curve intersection

Recommended Posts

I would need a way to calculate the intersection point between two bezier curves. the beziercurves have the 2d form from this article: http://www.gamedev.net/reference/programming/features/bezierpatch/ How would you calculate the point of intersection between two such curves. I would assume you could do it by getting the ''t'' value of intersection from one of the curves in some way and that would yield the point, the normal and everything... I want to do this the mathematical way - not by tracing the curve and testing approximations. I''m just not good enough at math... If i come up with a solution I will post it here.

Share this post


Link to post
Share on other sites
That gets rather nasty. Assuming cubic beziers you have three cubic equations for each curve, i.e. x = a1*t1^3 + a2*t1^2 + a3*t1 + a4 and similarly for y and z. You want where the x, y and z values are equal so you can equate the equations, i.e. a1*t1^3 + a2*t1^2 + a3*t1 + a4 = x = b1*t2^3 + b2*t2^2 + b3*t2 + b4. That gives you one equation of two unknowns, but you can do the same for y or z to get two equations of two unknowns. Solving that though is beyond me. It seems like you could move everything to the left hand side so that you have lhs=0 and then use the triatic formula to find the roots in terms of t2 where the a4 term would be a4-rhs, i.e. the roots depend on the value you choose for t2. That would give you three equations to plug into the second equation. That is going to be one nasty mess and I have serious doubts that you would be so lucky as to have that reduce to a cubic. If it did though you could use the triatic formula again to find the roots of the resulting equation in t2. That would give you nine values of t2 for nine potential points of intersection.

The most straightforward explaination of solving cubics that I could find is here. One thing to notice is that the coefficent on the cubed term is one. You certainly have a great deal of algebra ahead of you and I wish I could tell you that in the end it will be worth it. When you do the substitution into the second equation you may hit a brick wall though. That substitution is going to be a bear and short of someone that knows it is a dead end the only way to find out if it is a dead end is to do the substitution and reduce the resulting equation. Most likely it will not look like a cubic, but that won''t mean it is not a cubic. Getting it into a form that looks like a cubic may be a bigger accomplishment than solving the resulting cubic. Overall it might make for a very good arguement for using numeric approximation. I wouldn''t even attempt it without a CAS system like Mathematica, MathCAD, Maple, Derive or a similar package. I would expect it to take at least a day with a CAS system. Without it depends upon your rigor, methodology and knowledge. If you algebra is weak or you are careless in your work you might be at it for a very long time.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I once discoverd that solving a system of polynomals leads to solving single polynomals with a higher degree. I guess 3 cubic equations gives something like x^12 or so. And only polynoms with x^4 or less can be solved analytical.

Arne

Share this post


Link to post
Share on other sites
That would take some serious calculus. You might be able to solve the problem by taking the derivative of each function and then setting them equal to each other. If I remember my calc right, where the derivatives are equal, the base functions are equal (don''t quote me on it though, its been a while). Another non calc way might be thus... I don''t know a lot about bezier curves, so if any of those variables are actually constants that reduces the difficulty of the problem by a lot. Plug in any knowns as early on as possible. Then get the two equations in terms of one variable, say t1 as is listed below. Set them equal to each other and solve. I could be way off on that too. Good luck.

"You are too useless. And now I must beat you." - English subtitle in a Honk Kong Movie.

Share this post


Link to post
Share on other sites
quote:
Original post by lunarss
That would take some serious calculus. You might be able to solve the problem by taking the derivative of each function and then setting them equal to each other. If I remember my calc right, where the derivatives are equal, the base functions are equal (don''t quote me on it though, its been a while).


I really should quote your sig in your direction.

Calculus will neither help, nor work at all. If two derivatives are equal at a point, it means that the slopes of the functions are equal at that point

This is an algebra problem, nothing more.

Share this post


Link to post
Share on other sites
Thank you all...
I will probably approximate the curves with linesegments and have a recursive algorithm to find the ''exact'' point...

This is not the solution I wanted though - it would be much more general doing it the mathematical way....

the thing is - doesn''t the first solution with linesegments sound like using Secants (sekanter in swedish) and approximate the tangents of the intersection point.

Also - Where the Tangent of the first curve intersects the second Curves tangent at the same position as the tangents are located, is the intersection - I think this sounds pretty solvable ....

Please shower me with solutions and ideas...

Share this post


Link to post
Share on other sites
The recursive method sounds about right, or you can do it iteratively if you prefer that method. I'll play around with the bezier formula a bit today, and see if I find a more direct solution. Note that even if there is a direct solution, I can see no way that it will not involve solving at least one cubic equation (which requires complex numbers), so keep that in mind.

Would it be possible for you to use quadratic curves instead? They are much easier to solve.

EDIT:

I've done a lot of thinking, and I'm seriously doubting that there is a direct solution. Another complication is that two cubic bezier curves can have up to 9 intersection points. How should this be dealt with?

Edited by - Beer Hunter on November 23, 2001 12:51:42 AM

Share this post


Link to post
Share on other sites
Thanks - again....
I''d love to see a solution to this problem....
but it is not worth spending my time on solving this problem when there are alternative options that can be implemented right away....

well - if someone solves this in some smart way - it would be a great article to write

Share this post


Link to post
Share on other sites
The standard way to "solve" (its not analytical, but any precision you wish can be guarantueed) problems like this is interval arithmetic, but its slightly above the level of math Im comfortable with.

Edited by - PinkyAndThaBrain on November 28, 2001 10:54:44 AM

Share this post


Link to post
Share on other sites