Re: [ANN] WFBezierCombinatorics
Re: [ANN] WFBezierCombinatorics
- Subject: Re: [ANN] WFBezierCombinatorics
- From: Noah Desch <email@hidden>
- Date: Fri, 07 Mar 2014 23:26:45 -0500
Graham, I’d be glad to see how it performs with your additional test cases. Although I spent quite a bit of time handling special cases this is very much a work in progress and I appreciate any help anyone is willing to throw in.
I didn’t follow a specific algorithm, although much of the cubic bezier curve handling (bounding box computation, line-curve & curve-curve intersections, curve derivatives, etc) is based on the descriptions here:
http://pomax.github.io/bezierinfo/
In a nutshell, the algorithm I’m using is:
1) Walk the two input paths and add all their points to a vertex array
2) Compute intersections between the two paths and add them to the vertex array
3) Create two sorted index arrays which allow traversal of the polygons in order, including the intersections
4) filter out redundant intersections due to numeric imprecision and edge cases
5) Walk the sorted index arrays in order, building up the result bezierpath as you go, switching between the two index paths when you hit an intersection
6) Once you complete a polygon, pick the next starting point using some criteria determined by which operation (union,intersection,subtraction) you are doing.
Some notes…
Finding intersections between the two paths uses the naive n^2 algorithm. I’m aware there are better ones but the descriptions I could find mention only line segments and I am not sure how they generalize to curves.
Finding zeros of a cubic curve (used for curve-line intersections among other things) is currently quite inefficient and involves 100’s of iterations of Newton-Raphson. I recently came across a more efficient method that I will implement shortly.
Some of the unit tests in the project are not complete. I have verified their operation by examining the results in the debugger but writing assertions for dozens of vertices is quite tedious and I’m not done with that yet.
-Noah
On Mar 7, 2014, at 10:43 PM, Graham Cox <email@hidden> wrote:
> Hi Noah,
>
> Indeed, this is a potentially a very useful body of code.
>
> I have several implementations, some which flatten and others that do not, but the non-flattening cases are not always totally reliable. This can be a very hard problem to solve. I have a number of test cases that I can throw at the code that might show up problems - I'll be glad to give your code a whirl. Which algorithm did you employ?
>
> Thanks for doing this and making it available so cheaply (!) It's something that I've always thought should be part of NSBezierPath as standard (especially as Core Graphics must have the code in there already to calculate clipping path intersections).
>
> --Graham
>
_______________________________________________
Cocoa-dev mailing list (email@hidden)
Please do not post admin requests or moderator comments to the list.
Contact the moderators at cocoa-dev-admins(at)lists.apple.com
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden