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.