My First Curve-To-Curve Intersection Tests.
Finding the intersection of two lines is a fairly straightforward algorithm. You find their slopes, factor the equation, simple. But finding the intersection between two quadratic bezier curves doesn’t seem to have a simple equation. From the sources I’ve read (I’ll try and find them again so I can cite and quote them) curve-to-curve intersection can only be solved as an approximation.
There are a lot of cool things you can do once you have both line and curve intersections figured out. For example you can combine two shapes wherever they overlap. You can also do some less obvious things such as path offsets (equivalent to Flash authoring’s Modify > Shapes > Expand Fill)
There are several methods for this intersection approximation, but all of them reduce the curve into smaller (and flatter) curve segments, eventually performing a line-to-line intersection in place of the reduced curve segment. My first approach seems to be one of the faster methods for ActionScript, but maybe not.
Click and drag the handles in this demonstration:
The approach does a simple hit test between the bounding rectangle of each curve. This is a programmatic hit test, evaluating the control points of the curves in memory and doesn’t rely on Flash’s display list at all (which would be entirely too slow and unnecessary). If the curves’ bounding rects touch, then each is subdivided in half, tested against all the other subdivisions of the other curve, and subdivided and tested again where the hit tests succeed. You get the idea when moving the curves around in my test.
The source is available via right-click > view source, though I apologize I have no documentation whatsoever. I didn’t intend on blogging about this subject any time soon, but reading up on Jim Armstrong’s blog inspired me to start sharing and see if I can’t get any feedback. The approach is primarily where I want to hear any comments, positive or negative, and then I can clean up code for use later on.
[...] in quad. Bezier intersections, Tyler Wright has started an interesting project. You can check it out here. Also, here is a good paper contrasting various solutions to the general [...]
how do you get the boxes to draw inside the bezier when the two intersect?
follow-up question; where did you find the formula to draw the boxes that surround a point in the curve?
Jim – the boxes are just the bounding rectangle around the 3 points that make up the curves. Any bezier curve will fall directly within the bounds of these points. Wikipedia has a nice visualization: Bézier curve
So by dividing the curve in half and creating two new bezier curves of the one, you get two new sets of bounding rectangles that can be compared against the opposing curve.
I will always try to include the source for these posts. If you right-click on the example you can browse through the source code – sorry about the lack of documentation, this is something I did months ago, Jim Armstrong inspired me to drag it back out, and I haven’t had time to dig back into it to comment the code.
I see what you mean, I’ll dig through the code to see where exactly it’s happening. I’m juuust getting into doing more math stuff in AS3.
I’ve always had a lingering question though; say you see something basic like this: http://mathworld.wolfram.com/LogarithmicSpiral.html
and it shows you the formula for it, how does one possibly translate that formula into actionscript?
ha ha, great question! I suck at real math and I’m only marginally capable of code-math. I try and understand it conceptually first (visually), then try and break the equations down the best I can.
Here’s an example for ya, directly implementing the equation of the logarithmic spiral:
http://gist.github.com/462269