Port to VectorBoolean

[behdad]

We should port this module to use VectorBoolean instead of Clipper.

https://bitbucket.org/andyfinnell/vectorboolean http://losingfight.com/blog/category/graphics/

Main obstacle is that it's a Objective-C library. We should port to C++ (or ask Andy to do; I'm contacting him separately), but might be worth trying it out first. I managed to get it compiled on Linux using:

clang++ -fblocks *.m  -I /usr/include/GNUstep -I /usr/lib/gcc/x86_64-nux-gnu/4.8/include/objc -lobjc -lgnustep-base -lgnustep-gui -lBlocksRuntime

I had issues with blocks_runtime.h missing from my system, which I hacked around. The app doesn't run for me, but I imagine the operations work. It should be even easier to get it running on OS X. It's probably a weekend's work to hook this up to booleanOperations for someone comfortable with Objective-C, or a week for someone who isn't.

[adrientetar]

Skia does have vector boolean ops: https://www.youtube.com/watch?v=OmfliNQsk88

Maybe we can use it or extract the relevant code? cc @khaledhosny

[typemytype]

Boths seems promissing... but python bindings are really necessary in any case...

[behdad]

So we need someone who's comfortable with C++ and Objective-C to make a bridge.

[anthrotype]

or Swift... https://github.com/lrtitze/Swift-VectorBoolean

[behdad]

The Objective-C version at least I can compile on Linux using clang / gcc.

[anthrotype]

yes, sure. I just mentioned the swift version because it seems more recent, has a few tests, and the code may be easier to read than Objective-C.

EDIT: at least for me... :smile:

[adrientetar]

Behdad, do you dislike the Skia option?

It's battle-tested with fuzzing etc. probably the most robust vector boolean code out there. One has to extract the relevant source files from "core" and "pathops" subfolders and work from there.

[behdad]

I definitely don't like pulling all of Skia. I have not watched that video yet. Will do. I think extracting it would be much more work than porting the other project. I'll watch the video today; I'm also taking a look at the Swift version to see if I can just port it straight.

[behdad]

In general I'm skeptical of Skia getting this right. A lot of Skia vector code I've checked was just not there...

[adrientetar]

I think extracting it would be much more work than porting the other project.

I looked at it briefly and it seems relatively self-contained... mostly the vector ops depend on primitive types like SkRect/SkMatrix etc. and other ground stuff like SkArenaAlloc/SkBuffer.

A lot of Skia vector code I've checked was just not there...

idk, but in the video he says he first wrote boolean ops for QuickDraw GX in the 80s. I would think he has it right if he's been working on it for 30 years...

[behdad]

idk, but in the video he says he first wrote boolean ops for QuickDraw GX in the 80s. I would think he has it right if he's been working on it for 30 years...

Sure. I'll watch the video.

[behdad]

Yeah, I like the video.

[khaledhosny]

Why this is needed/wanted?

[behdad]

Why this is needed/wanted?

Because converting to lines, processing, and back, is slow and error-prone, and the Perfectionist's nightmare! :D

[khaledhosny]

I can give the extracting from Skia a try, but I’d know what to do with that code after that.

[behdad]

In the end, we want a point- or segment-pen that removes overlaps.

[behdad]

Thanks Khaled. I'll also talk to the Skia developer to see what his thoughts are.

[anthrotype]

I haven’t looked at the code, but from the video it looks like the skia shape ops converts cubic into quadratic to compute the intersections. We want to retain the cubics.

[adrientetar]

I can give the extracting from Skia a try, but I’d know what to do with that code after that.

I think basically we need a pen that builds an SkPath, then call the Op() function defined in SkPathOps.h, then the inverse pen.

[behdad]

I haven’t looked at the code, but from the video it looks like the skia shape ops converts cubic into quadratic to compute the intersections. We want to retain the cubics.

My understanding of the video was that it converts to quadratics to get a feel of the t, then works that back onto the cubic. I'm sure it doesn't convert to quadratics in the output.

[khaledhosny]

OK, I now have something that builds and runs, can take paths and return their union (or any path operation supported by Skia). All C++, no Python interface yet.

The bad thing is this is some 60000 lines of code, the good thing is that all is copied verbatim from Skia without modifications so should be easy to keep in sync.

[khaledhosny]

https://github.com/khaledhosny/skia-pathops, there is a simple Makefile and the code probably does not build on Windows/Mac.

[anthrotype]

Great! That was quick! :D I would like to keep the same python interface that booleanOperations has: that is, one function for each operation, which takes a list of UFO contours and a pointPen to draw the result on. Internally, we take the input contours, extract the segments using a pointPen, and get the resulting array of array of arrays, that we then feed to our C++ library and then we take the output and draw it on a the output pointpen.

If you have a Makefile that builds a shared library, I can make a quick wrapper for it using cffi or ctypes.

[anthrotype]

nice, the skia path objects have a pen-like interface very similar to our own! Maybe the python API can expose that directly.

[behdad]

Awesome. Thanks Khaled!

[typemytype]

super!

as far as I understand only the pathOps are extracted from the Skia project?

FYI: it does not build on mac 10.10 do you want the error message?

+1 for keeping the booleanOperation api

[anthrotype]

as far as I understand only the pathOps are extracted from the Skia project?

the whole skia tree is cloned as a git submodule, then we only build the part we need, which is pathops and some parts of the core.

We'll make it build eventually on all platforms. Please file an issue over at https://github.com/khaledhosny/skia-pathops

[behdad]

Also, did anyone consider AFDKO's impl? https://github.com/adobe-type-tools/afdko/blob/develop/c/public/lib/source/absfont/absfont_path.c

[anthrotype]

I didn't know that. what does that do?

[behdad]

Remove overlaps...

On Thu, Jul 26, 2018 at 3:35 PM, Cosimo Lupo notifications@github.com wrote:

I didn't know that. what does that do?

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/typemytype/booleanOperations/issues/40#issuecomment-408256079, or mute the thread https://github.com/notifications/unsubscribe-auth/AAIuK-qc5liVJR58RivPd_8uScl9uAbfks5uKkQ1gaJpZM4Ks_OU .

-- behdad http://behdad.org/

[anthrotype]

does any afdko tool actually use it? I'd like to see an example

[cjchapman]

@anthrotype Yes. It's used by mergefonts, rotatefont, & tx. Try searching on ABF_PATH_REMOVE_OVERLAP in the code.

[anthrotype]

oh.. I was using ripgrep to search instead of regular git grep; ripgrep also uses the .gitignore file to ingore files outside of VCS; but the .gitignore also lists tx and other compiled programs.. but that's also the name of the folder where the tx source files are located.. somehow rg excluded those from the grep. :grin: anyway, I'll have a look, thanks!

[cjchapman]

@anthrotype Ah. I think I need to fix .gitignore.

[typemytype]

confused now: this (absfont_path.c) is not or was not the same as old checkoutlines? what is the difference and has it the same logic as checkout lines. The main reason why booleanglyph exists was bugs in checkoutlines that somehow could not be fixed.

[behdad]

confused now: this (absfont_path.c) is not or was not the same as old checkoutlines? what is the difference and has it the same logic as checkout lines. The main reason why booleanglyph exists was bugs in checkoutlines that somehow could not be fixed.

Ah, ok. I was under the impression that Adobe did NOT open source checkoutlines and that's why you wrote booleanOperations.

I wonder what would have happened if we have pushed Adobe more to fix those bugs... So, you think that's a non-starter, even if Adobe is willing to improve it?

[behdad]

Checking how much code absfont_path.c is, I think it needs a lot more work indeed. It's just too short to be complete. Let's go back to considering SkPathOps. That seems to be the most complete solution around.

[adrientetar]

Yea, though ideally we need to get Cary Clark to look at https://bugs.chromium.org/p/skia/issues/detail?id=7682.

[typemytype]

@behdad BooleanGlyphs is older then opensourcing FDK. If Im remember it correctly checkoutlines was proprietary code (build for Illustrator, but current version are not using this). A huge amount of bugs and assumptions (fe when the area of a contour was to small it was just ignored... not good for any Thins or Lights) in that proprietary piece of code was the start of BooleanGlyphs by Tal and I

[jesusdesantos]

Just a suggestion for a library that could be useful here

https://github.com/verven/contourklip