Sunday, January 14, 2007

Set operations on paths

I'm virtually never excited about the things I have implemented. Partially because I've been working on computer graphics for quite a while and a lot of what I do comes down to doing things that I've done before for different software, or in a different scenario. Writing code while knowing exactly what problems you'll end up facing and how to solve each one of them is very mundane and it makes it hard to get excited about it once you're done. So whenever I have a little bit of time I try to sit down and implement something that hasn't been done before.

So, here's problem #1: one of my embarrassments in the Qt X11 engine is that fact that we don't do anti-aliased clipping there. So if you'll clip out a rounded rectangle in your viewport/widget it will leave out nasty jaggies on the sides. We do it correctly on Windows but not on X.

Main reason for why we haven't done it, is that Qt has this nice concept of combining clip-regions which requires basically a full fledged implementation of boolean set operations on polygons to work correctly.

And here's problem #2: in Qt we have this class called QPainterPath which is a resolution independent, geometrical representation of some rendering. We got reports from people saying it would be really great if people could use boolean set operations with QPainterPath's. And I agree. Set operations on QPainterPath's would be an incredibly powerful feature, especially for animations.

Requirements for a state of the art algorithm here would be: fast, works with all kinds of degeneracies and operates directly on paths without intermediate conversion to polygons. The issue is that none of those things is usually associated with set operations on polygons.

In 1998 a paper entitled "Efficient clipping of arbitrary polygons" was published by G√ľnther Greiner and Kai Hormann. It's a great paper, unfortunately the algorithm doesn't handle degenerate cases at all. This November Dae Hyun Kim and Myoung-Jun Kim published a paper entitled "An Extension of Polygon Clipping To Resolve Degenerate Cases" which addressed the shortcoming of the algorithm described by Greiner. The paper was a little short on details though so I've emailed Dae Hyun Kim who was kind enough to send me the full, original version of their papers. It's a tremendous paper and I'm very grateful to Dae Hyun Kim for sending me it.

Equipped with the paper I've sat down to modify the algorithm to handle paths, which was the last of my requirements for it. The research done in both papers was dedicated to polygons, while I wanted to apply it to paths, where curves are first class citizens. The main difference between polygons and paths. for the purposes of our new algorithm. is that with polygons any two segments can intersect in at most one point, with paths two arbitrary segments can intersect each other in at most 9 points. Furthermore with paths one segment can intersect itself. That plus a few smaller issues are causes of serious woes when working with paths in computational geometry - reason why basically no one does it.

Qt does now though. And yeah, I'm very excited about it. The new algorithm deserves a research paper of its own and if I'll have some spare time I'll definitely write a little bit about it.

I really needed this. I needed to do something that was very unique from a purely mathematical/computer science perspective rather than "oh, hey i fixed this bug/implemented this feature" type of stuff to keep me motivated. A screenshot showing a path (in dark gray fill and black outline) created from an intersection (boolean "And" operation) of two paths (the dashed blue and red objects) is shown below.

The number of effects and things that can be done with boolean set operations on paths is tremendous (not even mentioning the clipping :) ). You can be sure I'll write at least a few demos to show how to do very neat effects by differently combining few very simple paths.

11 comments:

Jacob Rideout said...

This is fantastic. Thank you Zach. Qt's graphic facilitates are quickly surpassing anything else that is available (at least that I know of) and we should see some terrific results about a year from now after application developers start releasing new Qt 4.3 apps.

Anonymous said...

Fascinating as always, Zack - glad you found some time to have fun and flex your Mathematical Mojo =). Qt 4.3 sounds like it will be a huge leap over 4.2!

jhernandez said...

your work is simply... Impressive!

Chandra Gondowasito 13504100 said...

Excuse me. Just wanna ask could you send me the full paper to dragon135@students.itb.ac.id.
I need it just to do polygon clipping.

Leonardo said...

Congratulations for your job.

Could you send me a copy of the full paper in leocda@gmail.com?

Thanks in advance.

Christian Brunschen said...

Apologies for leaving a late comment - I hope this reaches you. I am also very interested in getting a copy of the fill paper by Dae Hyun Kim and Myoung-Jun Kim, as well as learning more about your extension to the algorithm to also handle curves. I'm interested among other things in how you handle differences in how the subject and clip paths are colored (if one uses the non-zero, and the other the even-odd winding rule, for instance). (I could tell you what I want them for, but you'll laugh at me :) )

Best wishes,

// Christian Brunschen
firstname.lastname(at)gmail(period)com

Anonymous said...

Would you please forward me a copy of the full paper by Dae Hyun Kim and Myoung-Jun Kim. I haven't had much luck contacting them.

many thanks,
// Ryan Shipley
firstname.lastname(at)ngc(period)com

Anonymous said...

Hey Zack..your article about clipping is great and very useful. And I was wondering if I could have full copy of Polygon Clipping... pleeeaasse! you can send it to me in brixs@shaw.ca

Jay

st0le said...

This is exactly what i was looking for....

Please send me a copy of the full paper to st0lensoft[at]gmail[dot]com

Thanks in advance.

Brenor said...

I too would like to request a copy of the full paper.

Many Thanks,

Brenor Brophy
firstname(dot)lastname(at)gmail(dot)com

Brenor said...

I was able to track down one of the original authors Dae-Hyun Kim at:

cregeo(at)gmail(dot)com

He was kind enough to send me the copy of the original paper. It's essentially the same as the one linked above but with some welcome added details. With his permission its is available at:

http://getwx.com/Poly/Kim-Kim-Extended-Clipping.pdf