Re: Remove overlap on NSBezierPath
Hello, Thanks for you replies. To clarify: I need it in a small drawing app, where you can draw shapes and then you should be able to combine them. There is no outline but the winding is quite important (there may be overlapping, clipping and self intersecting parts). I did found DrawKit but as I need to keep the curves, this doesn’t seem to be an option. the precision of the location of the intersection points is not to important,as they are rounded to full integers – the shape of the curve shouldn’t change to much. I just had a short look at the Omni-OAExtensions. There are some functions to find intersections of paths, so I have to build my own merging routine out of it, right? Thanks again Georg___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to [EMAIL PROTECTED]
Re: Remove overlap on NSBezierPath
On 14 Jul 2008, at 7:48 pm, Georg Seifert wrote: Hello, Thanks for you replies. To clarify: I need it in a small drawing app, where you can draw shapes and then you should be able to combine them. There is no outline but the winding is quite important (there may be overlapping, clipping and self intersecting parts). If you don't need to draw the stroke, things maybe much easier (you could keep a list of contributing paths as part of some object of your own device for example). I did found DrawKit but as I need to keep the curves, this doesn’t seem to be an option. Right now I use GPC and (optional) curve fitting. It keeps the curves in terms of their appearance but can greatly alter the number and location of the control points. I don't like it much either - one reason I'd love there to be a great solution built-in. Unfortunately I'm no mathematician and so I haven't been able to come up with a great way to do it from first principles, nor found any suitable code out there until... I just had a short look at the Omni-OAExtensions. There are some functions to find intersections of paths, so I have to build my own merging routine out of it, right? ...this. I hadn't seen those before either. It looks as if they've given away the hardest part, finding the intersections and crossing directions of each intersection. On top of that you can build the set operations. I plan to have a very good look at doing this for DK as soon as I can - if it can be made to work it will be a much better solution than curve fitting. Props to the Omni guys for being prepared to give away this code like this :) cheers, Graham___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to [EMAIL PROTECTED]
Re: Remove overlap on NSBezierPath
What the mathematicians balk at isn't the pathological cases; rather, getting exact results. But the real problem is that these two are related. I spent several years fixing the Boolean operations for a major CAD company's solid modeler (the long-gone ComputerVision) which is essentially the same problem made much more difficult by doing it in three dimensions. The basic algorithm is conceptually simple: 1.) find all the intersections 2.) break into pieces at the intersections 3.) decide which pieces you need on the basis of some in/out tests and which set operation you are doing. 4.) assemble the final result The hitch is that #3 is a bunch of yes/no decisions that you must make on the basis of imprecise floating point operations in #1. And all the results of #3 have to be consistent or #4 won't work properly. This is trivial in the easy cases (curves intersecting at reasonable angles, no tiny pieces) but *VERY* hard to get right for the arbitrary case (tangencies, near-tangencies, overlaps, pieces of curve that come out smaller than whatever numerical tolerance you are using for your floating point approximations, etc.). Essentially you have to have some checks on the final result and be prepared to fail gracefully. RObert Clair ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to [EMAIL PROTECTED]
Re: Remove overlap on NSBezierPath
On 13 Jul '08, at 6:43 AM, Georg Seifert wrote: How I can merge to bezierPaths and remove the overlap in Cocoa. Does anyone has exerience with this or can point me to some information? That's a rather difficult bit of computational geometry. AFAIK, CoreGraphics doesn't have anything that does that. (Back in 1994 I implemented code for doing boolean union/intersection operations on arbitrary polygons, which is a simplified case of what you're asking. It was extremely difficult, even though I was only implementing an already-published algorithm. I don't recommend it.) —Jens smime.p7s Description: S/MIME cryptographic signature ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to [EMAIL PROTECTED]
Re: Remove overlap on NSBezierPath
Are you talking about performing union, intersection, difference (i.e. set operations)? If so, this is not a simple problem. Cocoa doesn't have anything built in to do it, and in fact there is no known general solution for arbitrary bezier curves (though there are plenty of practical/heuristic methods that work for most practically useful cases, and I for one would love to see these as part of CG, as they are part of Java, Flash, etc). In the meantime, there is a general solution for vector paths (i.e. paths that consist of short straight line segments) and you can flatten a bezier path to one of these easily. One of the best implementations I've run across is General Polygon Clipper by Alan Murta (http://www.cs.man.ac.uk/~toby/alan/software/) - free for non- comercial use but not for commercial use. I have written some straightforward categories on NSBezierPath that translate NSBezierpaths to and from GPC's internal representation and also provide some high-level methods to directly perform set operations. This code is part of DrawKit (http://apptree.net/drawkitmain.htm) and also covered on CocoaDev here: http://www.cocoadev.com/index.pl?NSBezierPathcombinatorics hth, Graham On 13 Jul 2008, at 11:43 pm, Georg Seifert wrote: Hello, I don’t know if this is the right place to ask ... How I can merge to bezierPaths and remove the overlap in Cocoa. Does anyone has exerience with this or can point me to some information? Thanks in advance Georg___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) 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: http://lists.apple.com/mailman/options/cocoa-dev/graham.cox%40bigpond.com This email sent to [EMAIL PROTECTED] ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to [EMAIL PROTECTED]
Re: Remove overlap on NSBezierPath
How I can merge to bezierPaths and remove the overlap in Cocoa. Does anyone has exerience with this or can point me to some information? It's not going to solve this problem generally for you, but you could start with the code provided generously by Omni: http://www.omnigroup.com/developer/ and in particular, the NSBezierPath-OAExtensions category in OmniAppKit/OpenStepExtensions, which provides a few extra useful functions for operating on Bezier curves. Cheers, Brett ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to [EMAIL PROTECTED]
Re: Remove overlap on NSBezierPath
On 13 Jul '08, at 9:14 PM, Graham Cox wrote: Since apps like Adobe Illustrator and Flash can perform these operations on bezier paths, clearly there are methods that exist for doing it, even though the mathematicians claim otherwise (what they are claiming is the lack of a general all-purpose solution to the arbitrary intersection of bezier paths, but for real-world graphics there wouldn't be too many pathological cases to worry about). What the mathematicians balk at isn't the pathological cases; rather, getting exact results. It's not possible to find the exact points of intersection of cubic curves, because it requires factoring a sixth-order polynomial, for which there are no known general techniques. The best you can do is to find approximations, using algorithms like Newton's Method. You can make the approximations as precise as you need by increasing the number of iterations. That's what existing programs do. —Jens smime.p7s Description: S/MIME cryptographic signature ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to [EMAIL PROTECTED]
