Graphical polygon operations (stroking, clipping etc)

[pappis]

(I’m not sure under which category to post this, but I post it here since I am a OF newbie.

I am trying to do several polygon-related things with openFrameworks, which I haven’t been able to figure out how to do using the built-in tools in OF.
Basically, I use ofxOpenCv to track shapes in a video stream, and want to do graphical things to the resulting blob polygons.

First, I want to stroke polygons (draw a polygon outline) using thick lines. Since openFrameworks uses OpenGL to implement drawing this doesn’t really work since OpenGL doesn’t really support stroking polygons, it just draw each segment as a separate line with no joins. I know of several graphics libraries that implement this by creating a new polygon containing the stroked outline and then filling that polygon, but I haven’t been able to find any easily isolated code to do that. I think there is code to do this in the Antigrain graphics library for example, but it’s not easily extractable, at least not for me.
Does anyone have any hints on how to stroke polygons with thick lines using openFrameworks? Preferable with controllable joins (miter/bevel/round) and line caps (round/butt/projecting square).

See the attached image for a visual description of what I want.

Also, I want to do binary/set operations on polygons like intersection (clipping), union and subtraction. This is for several purposes. One is simply to clip drawing to a polygon (so that all drawing while the clipping is in effect will be intersected with the clipping polygon). I guess you could use OpenGL’s stencil buffer to do this? I also would like to do hit testing of polygons against other shapes.
I have found a polygon clipping library called the Generic Polygon Clipper library (http://www.cs.manchester.ac.uk/~toby/gpc/), which can do polygon intersection/union and subtraction. I have written a small OF add-on that wraps this library (let me know if anyone would like a copy). This basically solves this part of my problem, but the GPC library is only free for non-profit uses, which could be problematic for me in the future, so I would prefer to find another solution, if possible.

Finally, I would like to perform polygon offsetting operations (expanding/shrinking a polygon) and be able to find the straight skeleton of polygons. The boost polygon library can expand/shrink polygons, but doesn’t support floating point coordinates + it’s a big complex system. Then there is the Computational Geometry Algorithms Library (http://www.cgal.org/) which implements these kinds of things, but as far as I can tell, the parts of CGAL that I’m interested in is licensed using the QPL license, which seems very problematic for me to use. (As far as I can tell it’s a “viral” license that would require me to release the full source of anything I do using CGAL under the QPL license. Since I don’t own all the source code I use (like openFrameworks for example), I guess I can’t do this.)

I hope I managed to explain what I mean. Thanks in advance for any help!

/Jesper


[angusj]

Hi Jesper.

This basically solves this part of my problem, but the GPC library is only free for non-profit uses, which could be problematic for me in the future, so I would prefer to find another solution, if possible.

http://www.angusj.com/delphi/clipper.php
http://sourceforge.net/projects/polyclipping/

Angus (author of Clipper)

ps: Clipper also supports polygon offsetting.
pps: Clipper requires coordinates as (long long) integers to facilitate numerical robustness, but it’s a simple task for the programmer to scale floating point coordinates to and from integer values.
ppps: Antigrain Geometry (http://www.antigrain.com/) does a much better job of polygon rendering than openGL IMHO. Another alternative to openGL is Cairo (that also supports mitred and rounded line joins) which I think is also bundled with openFrameworks. There are demos in the Clipper package that use each of the above graphics rendering libraries - ie openGL, AGG and Cairo - plus others.

[pappis]

Angus (author of Clipper)

Excellent, thank you! I’ll take a closer look at it tomorrow, but it seems your library solves all of my clipping (and probably offsetting) needs! And it is self-contained and doesn’t do lots of lots of other things, exactly what I was looking for. Thanks again!

/Jesper

[pappis]

Hi again!

http://www.angusj.com/delphi/clipper.php
http://sourceforge.net/projects/polyclipping/

Angus (author of Clipper)

ps: Clipper also supports polygon offsetting.
pps: Clipper requires coordinates as (long long) integers to facilitate numerical robustness, but it’s a simple task for the programmer to scale floating point coordinates to and from integer values.
ppps: Antigrain Geometry (http://www.antigrain.com/) does a much better job of polygon rendering than openGL IMHO. Another alternative to openGL is Cairo (that also supports mitred and rounded line joins) which I think is also bundled with openFrameworks. There are demos in the Clipper package that use each of the above graphics rendering libraries - ie openGL, AGG and Cairo - plus others.

Now I have finally had time to take a good look at Clipper, and it works fine for me! Both clipping and polygon offsetting work the way I want them to (except possibly for shrinking polygons, but that isn’t as important for me).

Now, I only have to find a way to generate stroked polygons, too.

(I agree with you about Antigrain and Cairo generating much nicer results than straight OpenGL (though being a Mac guy I’d probably go for CoreGraphics/Quartz directly instead), but I will try to stick with OpenGL for the time being.)

Thanks again!
/Jesper

[joshuajnoble]

I’ve used AGG and I can attest: pretty sweet lines though I think Cairo is the standard. As of 0062 Cairo isn’t included but it’s going to be supported in 007 (which should be released any day now), just as FYI

[pappis]

Now, I only have to find a way to generate stroked polygons, too.

In case anyone else is interested in this: I ended up using Apple’s CoreGraphics library (specifically CGContextReplacePathWithStrokedPath() to create a stroked version of a path, and CGContextCopyPath()/CGPathApply() to read back the generated path vertices) to get the polygon -> stroked polygon functionality. I’d be happy to share my code if anyone else wants it, though as noted above, it’s Mac-only.

/Jesper

[ikishchak]

See PolygonLib - Polygon Clipping Library.
This is C++ and COM library with good performance and many boolean operations.
Here is performance comparison with 2 well known Polygon Clipping Libraries.

[pappis]

See PolygonLib - Polygon Clipping Library.
This is C++ and COM library with good performance and many boolean operations.
Here is performance comparison with 2 well known Polygon Clipping Libraries.

Thanks for the reply!
As far as I can tell, PolygonLib offers similar functionality to the Clipper mentioned above. However, since I am a Mac user, PolygonLib isn’t an option for me (since it seems to be a binary-only library built for Windows). Also, I’d prefer a non-commercial, open source library.