Parametrized stroke outlining / expanding / offsetting

[strandedcity]

I've been following the library for some time, and have started a spare-time project based on it. I've been eagerly interested in the functionality to expand strokes into paths, particularly for bezier curves (where I know the problem is mathematically complex). Has a strategy / timeline for implementation been discussed? I may be able to contribute if new contributors are welcome.

I wasn't sure if the "outline" feature was separate from what I would describe in a CAD world as "offset". Is there some way to get equations for the position of the stroke edge that is not as complex as a full bezier-offset solution? See http://pomax.github.io/bezierinfo/#offsetting for a very detailed explanation of the math involved.

Thanks!

[christophknoth]

@pseaton

The Roadmap says it is planned: "Parametrizable path offsetting / stroking, to expand strokes to outlines and optionally produce all kinds of expressive strokes easily." @lehni probably has already some ideas for it and I am also interested in that topic. But more from a calligraphic point of view.

When smoothing will work sufficiently outlining would be the next thing I would concentrate on. Until then you are a bit on your own I guess. But I think contributions are always welcome anyways!

[christophknoth]

A friend pointed me to a pdf that could maybe be a useful starting point in this topic:
Variable width splines: a possible font representation? by R. Victor Klassen

[strandedcity]

Very interesting approach. I have always thought of the two edges of font characters to be somewhat independent of each other, though I suppose there's always a centerline that could be reverse-engineered.

It sounds like the question of how this is done programmatically is still up for some debate. In the world of offsets there are lots of problems in the forms of singularities, loops, corners, etc, all of which are compounded by the lack of a clear and consistent mathematical formula connecting a given curve and its offset, except in rare degenerate cases.

I'll see if I can work up something useful when I get a moment. I'm a little underwater with lots of projects right now, but I'll get back to it soon. Thanks for the reference, and the replies!

[christophknoth]

@lehni @pseaton
I found a paper called Vector Graphics Stylized Stroke Fonts by Philip J�agenstedt. Look especially at chapter 5: Extended Stroke Model where he describes his ideas. He writes in his blog that he implemented a stroking algorithm for canvas in opera in 2008. But I am not sure if it was ever out in the open. He works for chrome now, so maybe they open source the code one day ;)

But he also did not solve some problems that appear with his implementation like shown in chapter 10.

[christophknoth]

@pseaton I just found two other example made by Pomax where he put his math into action:

Here you can click to generate a random curve and see his outline algorithm. It works quite ok but fails in some edge cases:

And he made a nice little stroke-based CJK character builder that also works quite nice if you don't trick it too much:

It also supports changing the thickness and different stroke endings:

[christophknoth]

Quadratic bezier offsetting with selective subdivision! by Gabriel Suchowolski, Jul 10, 2012

[microbians]

Thanks a lot @christophknoth

UPDATE: Ported from SWF to Canvas 😉 and added variable offsetting

Here is a dirty demo in flash (is an old demo): http://microbians.com/?page=code&id=code-bezieroffsetingplayground

And a drawing application on I use the paper bu with variable offseting.
http://microbians.com/?page=code&id=code-theelectronicsketchbook

I will release the code soon ;)

[lehni]

@hkrish is working on a precise implementation of this that works better than the approach described by Pomax. I'm not sure how far away it still is.

[hkrish]

This has been in the works for some time. One of our main references was the paper http://visualcomputing.yonsei.ac.kr/papers/1997/compare.pdf, comparing different methods for offsetting planar bezier curves. And we chose the adaptive least squares method by J. Hoschek.
The method is detailed in https://dl.acm.org/citation.cfm?id=55191 (behind a paywall)

I had made this demo/test page some time ago. The method is actually quite simple, general (least-sqrs and subdivision) and naturally extends to variable offsetting etc. You can check it out at,
http://hkrish.com/playground/paperjs/offset/offsetStudy.html Warning: the script may freeze your browser in some cases. The curve intersection and boolean code has since been rewritten in paperjs, so most of it's problems are solved, but the demo is still using an old build of paperjs.

As long as we are working on just one cubic bezier segment most of these methods perform well, and definitely Hoschek's is one of the most performant and precise. However everything is downhill from there onwards —I am talking about linking up individual curves while making sure we are not breaking continuity between adjacent curves and discarding invalid parts when we offset a piecewise bezier curve; and in paperjs, we need to have a method that is robust and fast enough to handle most of, if not all, the corner cases.

Hoschek's method has another advantage that it allows us to keep the tangent continuity between two adjacent paths. The methods outlined by Pomax (seems to me that it is an extension of Cobb's method "Design of Sculptured Surfaces Using The B-spline Representation", I may very well be wrong here!), although simple, may not suit our purpose well (see the comparison paper for details).

I am hoping to finish this up in a week or two.

P.S. @lehni I think I can send some code your way before Easter. :)

[christophknoth]

@hkrish Exciting!

[lukeaskew]

+1 for this functionality

[lehni]

Yes we're working on it. It'll take more time.

[davelab6]

@hkrish did you publish the code anywhere? :)

@lehni any news? :)

[iconexperience]

I have been working separately on this issue using a different approach than Hari. Instead of creating the outer offset and inner offset path, I cut the path into curves. Then I subdivide each curve into several parts and apply an offset algorithm to each subcurve. Finally the offsets of all subcurves must be combined.

The code for the subdivision of a cubic curve and the offset algorithm for the subcurves is more or less finished. After cleaning it up a bit I will post it here, so we have a second starting point for implementing the path offset feature. So far it looks like the implementation works for an arbitrary cubic bezier curve and IMHO the result is quite satisfying. The whole algorithm is rather simple, which on the other hand makes it quite fast. Here are two examples:

But there is one remaining obstacle:
In order to have a clean result for the offset operation, the offset paths for the subcurves need to be combined to one single path. But unfortunately the current implementation of the boolean path operations do not produce the expected results.

@lehni or @hkrish, do you see any chance that the boolean operations can be improved, so they can handle overlapping paths, self intersecting paths, and in general produce more predictable results (the usage of a random number seems to produce, well, random results :-))? I think if the issues with the boolean operations can be solved, there is nothing that can stop Paper.js from getting a very nice path offset feature.

Thanks,

Jan

[hkrish]

Your code seem to work pretty well for single curves; how does it work for paths?

Anyway, I need to focus a bit on the boolean code. We have the basics in place to remove the dependency on random (a new cubic solver etc.). I will hopefully get some time these coming weeks, and keep you guys updated.

/hari

On 2014Oct16, at 07:50 pm, Jan notifications@github.com wrote:

I have been working separately on this issue using a different approach than Hari. Instead of creating the outer offset and inner offset path, I cut the path into curves. Then I subdivide each curve into several parts and apply an offset algorithm to each subcurve. Finally the offsets of all subcurves must be combined.

The code for the subdivision of a cubic curve and the offset algorithm for the subcurves is more or less finished. After cleaning it up a bit I will post it here, so we have a second starting point for implementing the path offset feature. So far it looks like the implementation works for an arbitrary cubic bezier curve and IMHO the result is quite satisfying. The whole algorithm is rather simple, which on the other hand makes it quite fast. Here are two examples:

But there is one remaining obstacle:
In order to have a clean result for the offset operation, the offset paths for the subcurves need to be combined to one single path. But unfortunately the current implementation of the boolean path operations do not produce the expected results.

@lehni or @hkrish, do you see any chance that the boolean operations can be improved, so they can handle overlapping paths, self intersecting paths, and in general produce more predictable results (the usage of a random number seems to produce, well, random results :-))? I think if the issues with the boolean operations can be solved, there is nothing that can stop Paper.js from getting a very nice path offset feature.

Thanks,

Jan

—
Reply to this email directly or view it on GitHub.