Paper.js: 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 Jagenstedt. 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 [email protected] 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.

[iconexperience]

@hkrish The code only produces outlines for single curves. But since a path is simply a chain of curves, the offsets for the path can be created with applying the boolean unite on the curves' offsets.

The only problem are the corners at the path segments. When iterating through the curves of a path, handling the corners could be done like this:

• After creating the offset for the subcurves, check if the handle-in and handle-out of the original end segment are parallel.
• If parallel, nothing needs to ne done, the ends of the adjacent curve offsets will match.
• If not parallel, add a little triangle to the last subcurve's offset to fill the gap to the next curve's offset. The line between the open ends can either be straight (bevel corners), an arc (rounded corners) or a straight extrapolation of the tangents (mitered corners). Creating this triangle should be relatively easy.
• The boolean operation (that we need to apply anyway to unite the offsets of all curves) should then be able to unite the curve offsets seamlessly, as the end of the curve offset will match the beginning of the next curve's offset.

Here is a (not very good) illustration on where the triangle needs to be:

Actually, I think the really difficult part is to resolve the issues with the boolean operations. I would love to help, but I fear that this goes beyond my capabilities. One thing that I can do is trying to implement the corner handling described above to see if it works.

Jan

[davelab6]

Maybe @frank-trampe can help with the boolean; he worked on FontForge's this year for me, and there's also http://www.angusj.com/delphi/clipper.php which is used in RoboFont

[lehni]

@iconexperience, very interesting! I look forward to seeing it all in action. Your plan how to merge the curves sounds good. We'll have to see how the two approaches perform and how precise their results will be. Boolean operations will also be required to handle strokeCap, for either solution. And the mentioned issues with the boolean code are well known, it's just a question of available time at the moment to fix them.

@davelab6, @frank-trampe, help is always welcome! But as far as I understand, Clipper only handles polygons, not bezier curves, so it won't be of much use here.

[davelab6]

On 17 October 2014 00:28, Jürg Lehni [email protected] wrote:

@davelab6 https://github.com/davelab6, @frank-trampe
https://github.com/frank-trampe, help is always welcome! But Clipper
handles polygons, not bezier curves, so it won't be of much use here.

Its used in RoboFont on Bezier paths, via
https://github.com/typemytype/booleanOperations

[lehni]

@davelab6 yeah but it looks like the paths are flattened beforehand, which is far from ideal, no?
(with flattening I mean conversion to line segments through sub-division: https://github.com/typemytype/booleanOperations/blob/master/Lib/booleanOperations/flatten.py)

[kuribas]

I have written code for calculating an offset curve from a bezier curve in haskell:
https://github.com/kuribas/cubicbezier/blob/master/Geom2D/CubicBezier/Approximate.hs
My code takes a discrete number of samples from the offset curve, and approximates a bezier curve through them. If the tolerance of the curve is larger than a given tolerance, I subdivide where the error is largest. To approximate, I calculate a least squares approximation, using the chord lengths as parameters, then improve the parameters by making a new guess of the parameters. I repeat this process until it converges. I have found a way to make it converge much faster by improving the guess of the parameters. It will give the best least squares approximation of the curve. For subdivision I just take the point with the largest error, by checking discrete number of samples.
The offset curve has a singularity when the radius of curvature and the offset distance are equal, so I find these points by solving an equation numerically, and use them as endpoints for the bezier curves.
I have not made a comparison with other algorithms, but it seems to work fine. Alternatively you could calculate a hermite spline interpolation from the offset curve. It may give more subdivisions, but is possibly faster than my algorithm. I haven't tested this yet... It seems that the lib2geom library, used by inkscape, uses this approach by converting to the symmetric power basis.

For boolean operations I am working on a line sweep algorithm, which will work in (n+m)log(n+m) for n points and m intersections. It's an adaptation of Bentley Ottman (http://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm), and uses the bezier clipping algorithm for finding intersections (http://tom.cs.byu.edu/~557/text/cagd.pdf).

[kuribas]

I forgot to mention that Chebychev polynomials also are a good candidate for interpolation. They have the good property of keeping the maximum error minimal (rather than the mean error when using least squares). It may be interesting to compare these different approximations for speed and accuracy. For real-time use, a faster algorithm that generates many bezier curves may be better, while for generating an output file, a slower algorithm that has better accuracy may be desirable.

[kuribas]

A rough outline of my boolean operations algorithm can be found here: http://kuribas.github.io/omegafont/algorithms/overlap.html

[hkrish]

Hello @Kristof, for offset curves, we chose the method due to Hoschek et.al.
after the comparison done at http://dl.acm.org/citation.cfm?id=618434.
Hoschek's method is conceptually simple and quite performant. Thanks for
the input (Hoschek's method is quite close to what you described above). I
guess we can benchmark it eventually on local offsets. _Although_, the most
difficult part was the global offset.

All those edge cases!

Our presently-unfinished implementation in paper.js is complete and quite
fast while doing local offsets. Most of the work has to be done at the path
level. So I am really looking forward to see how we can solve some of the
issues related to global offset. I will write a post here with specifics.
All suggestions are welcome. I am almost out of ideas here :)

Again, @Kristof, the sweep-line boolean ops sounds awesome. I am really
excited to know that you are working on it. That seems to be the right
approach. I have been outlining a similar approach for using a sweepline to
do boolean operations, just like they do for polygons. Bentley–Ottmann's or
Balaban's are great references. I am trying to implement an efficient
multiresolution curve datastructure to support the algorithm, since in this
case the curves has to be split so that they are monotonous in x and y.
(curious to see that in your case you are splitting only in one direction.
We should exchange notes, I think I can learn a lot from you progress so
far. :))

Although as a first priority I am committed to solving the problems in
paperjs' current boolean implementation. If any of you are interested in
joining me, that would be really nice. Please ping me, I will explain how
it works, and what are the issues we have found so far.

I have a question related to this, any information regarding this is
welcome. Many of the "surprises' in our boolean implementation are due to
loss of precision in the floating point arithmetic involved. Specifically
so when really odd sized curves are created as part of splitting etc. Many
CAD and illustrator like softwares seem to include a "precision" parameter
for boolean ops. And we know that the polygon implementations use "snap
rounding". So, have anyone tried snap rounding beziers? Are there any good
algorithms or case studies?

Thank you.

/hari

On Fri, Oct 17, 2014 at 3:38 AM, Kristof Bastiaensen <
[email protected]> wrote:

A rough outline of my boolean operations algorithm can be found here:
http://kuribas.github.io/omegafont/algorithms/overlap.html

—
Reply to this email directly or view it on GitHub
https://github.com/paperjs/paper.js/issues/371#issuecomment-59438784.

[kuribas]

hi @hkrish. If I am not mistaken, the Hosheks method is similar to mine, except that I try to improve the guesses of the sample points for calculating the least squares solution. This is slower, but gives a more accurate curve. This matters for me, because I want to calculate the least amount of subcurves, and speed is secondary for my application.

I think snap rounding may work for bezier curves. In my algorithm I used snapping to other points, but the algorithm gets very complicated, so it may be worthwhile to look at snap rounding instead. The important thing when rounding is to look out for changes in topology, because they may cause errors in the output.

If I can help with your current issues, let me know.

[lehni]

@hkrish, @kuribas do you think both methods could perhaps be combined, with a optional argument that decides weather the algorithm should be optimizing either for speed or quality of the resulting curves?

When experimenting with the code that @hkrish has already written, one of the remaining concerns I had was the production of too many sub-curves under certain circumstances. If the two approaches could be combined, that would be ideal! @hkrish, is it too early to share code? Would a collaboration make sense here?

(Not intending to step on anyone's toes here, just really excited about the activity in this thread : )

[iconexperience]

I have created a Plunker for my code on offsetting a single cubic bezier curve.

You can drag the end points and handles of the curve, zoom in and out (+ and - key), pan (arrow keys), and change the offset distance. I found playing around with it to be quite addictive.

You can find the plunker here: http://embed.plnkr.co/jkNGoe8fD0li9DmY7u76/

(note that there seem to be problems with Safari and Internet Explorer)

My aim was to have a starting point for creating curve offsets that are visually "good enough" with breaking the curve into as few sections as possible. My aim was not to create mathematically precise offset curves, so please do not use any of this code for technical applications.

The result is far from perfect, parts of the code are rather clumsy and the mathematics are not very sophisticates, but it allows changing parts of the algorithm quite easily, so if you like to tinker around a little bit you may find this useful as a simple base application.

Some details about my algorithm:

• First I break the curve into segment curves at the inflection points and the points that I call "peaks". These peaks are the roots of the cross product of the first and second derivative of the curve. They are especially usefull if the curve has a loop. Finally I break all sections that have an angle larger than 60° into smaller sections. There is no specific reason why I chose 60°, it just seems to work well.
• For each section I create two offset curves, one with positive and one with negative offset. I am using an algorithm that keeps the angles at the end points and the distance at t=0.5. I tried some other algorithms (like Tiller-Hanson), but this seems to give me the best overall results.
• The two offset curves are connected with straight lines at the ends.
• Finally, I can merge the section offsets into one single path, which may have self intersections.

What I cannot do at the moment is to take the merged offset path and remove all the self interesections. If someone can point me to a document that shows how this can be done, I would be very thankful.

That's all for now, I hope you enjoy playing around with it.

Jan

[davelab6]

What I cannot do at the moment is to take the merged offset path and remove all the self interesections. If someone can point me to a document that shows how this can be done, I would be very thankful.

@kuribas wrote above on this topic,

For boolean operations I am working on a line sweep algorithm, which will work in (n+m)log(n+m) for n points and m intersections. It's an adaptation of Bentley Ottman (http://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm), and uses the bezier clipping algorithm for finding intersections (http://tom.cs.byu.edu/~557/text/cagd.pdf).

and he also did http://kuribas.github.io/omegafont/algorithms/overlap.html :)

[lehni]

@iconexperience I haven't seen your plunker before, it looks really good! If I understand correctly, the main issue that's stopping you is in the boolean operations code, correct?

[iconexperience]

@lehni Yep, a fully working boolean code would solve almost all the remaining issues. There are some edge cases that would need a little work elsewhere, but a boolean code that really works would be a dream come true.
I am extremely busy at the moment (a few days before new product release), but if there is something I should test I will try to arrange a little free time. In a few weeks I should be able to contribute again to PaperJS.

[lehni]

@iconexperience that's great to hear. There are still real issues remaining in the boolean code, mainly #449 and #450. Unfortunately I haven't heard from @hkrish in quite a while, not sure if he's still working on this other approach or not. We could attempt fixing this in the current code-base together? Your code in #648 would probably be of use here?

[lehni]

@kuribas I finally wanted to look at your outline of the boolean code posted in https://github.com/paperjs/paper.js/issues/371#issuecomment-59438784, but that page is gone. Has it moved elsewhere? Would you be interested in joining the effort of implementing proper boolean operation code, as well as offsetting in paper.js?

[kuribas]

I am currently debugging my sweep line algorithm for set operations on paths. It's written in literate haskell, and hopefully clear enough to understand the workings. I'll upload the file when I am finished.

As for offsetting, I have found an algorithm to quickly find the best parametrization for a least squares fit. I then use a binary search to find the best nodes to subdivide. It is still rather slow, so probably not very useful for real-time applications. In my tests a least squares solution with a simple approximate parametrization and subdividing the curve will give good enough results (which I believe is what you are doing now?)

My javascript knowledge is limited, but if you need help understanding my algorithm, I am glad to provide it :-)

[kuribas]

For finding intersections I use the bezier clip algorithm (http://tom.cs.byu.edu/~557/text/cagd.pdf).
My implementation is here: https://github.com/kuribas/cubicbezier/blob/master/Geom2D/CubicBezier/Intersection.hs
An alternative (faster) way is implicitization. It would reduce intersections to finding the root of a maximum 9th degree polynomial, which can be solved by http://ir.nmu.org.ua/bitstream/handle/123456789/111417/40ffff39f2dd54b3467a4431e412d181.pdf?sequence=1
I am considering using that if the intersections are a bottleneck.

[kuribas]

That last paper is also interesting since it contains the closed form formulas for finding roots of 3rd and 4th degree polynomials, which is quite a bit faster. For example finding the intersection of a line and a bezier curve reduces to finding the root of a 3th degree polynomial, which I am using in many places.

[microbians]

Sorry to insist, but for offseting and squares fit I think could be useful read my paper ;)

http://microbians.com/?page=math&id=math-quadraticbezieroffseting

I know my english is terrible, but I think is a very fast algorithm, with a loop of 3 subdivisions the offsetting is more than usable and very fast, here is a guy that do a html5 test using my algorithm:

http://brunoimbrizi.com/unbox/2015/03/offset-curve/

He do it using only one interaction of the subdivision, but if you do two you can arrange a very good aprox.

My flash example (sorry is flash and old) http://microbians.com/?page=code&id=code-bezieroffsetingplayground

But the thing with bezier clip, boolean op, and that is another story ;)

[lehni]

@microbians your approach looks great, but works for quadratic curves. Since we're dealing with cubic curves in paper.js, I have a feeling we need a different approach. We could of course convert cubics to quadratics first, but that's not a trivial problem either.

[lehni]

@kuribas Unfortunately I'm not fluent at all in Haskel, so we'll have some language barriers both ways. I am looking for a fast approach indeed. Did you see @iconexperience proposal? It appears to produce very nice results. I'm curious to hear your thoughts on the math behind it.

[lehni]

@iconexperience I've been playing with our code quite a bit now and am impressed so far with how it behaves. I'd be curious to find out why your approach produces good peaks, and how you go there : )

"The peaks are calculated by finding the roots of the dot product of the first and second derivative. Actually I am not entirely sure what I am doing here, but this function works pretty well in providing good split points for the curve."

[lehni]

@iconexperience regarding the merging of the outlines of the separate curves to full paths, as outlined here https://github.com/paperjs/paper.js/issues/371#issuecomment-59381879:

Due to requirements in hit-testing, there is code already that can create bevel join and square cap geometries, see Path._addBevelJoin() and Path._addSquareCap(). I've designed these with path offsetting in mind, so they will come in handy when producing the paths to be used for the boolean ops. The only part missing is round joins, but that can be handled with out boolean operations, simply by drawing a connecting arc. I have this all pretty clearly mapped out, so once the boolean operations can handle touching paths, we should be ready to go!

[kuribas]

The math looks fine to me. The offset curve however can also have singularities at different points as the curve itself.

[kuribas]

It would be nice to see the difference in number of curves between your algorithm and a simple midpoint algorithm (for a given tolerance).

[lehni]

@iconexperience while working on fixing the boolean operation issues, I had and idea for how to handle path offsetting along stroke outlining in a way that would not even require the operations here. Let's work on both, so v1.0 can finally roll out!

[iconexperience]

@lehni
I have updates my plunker to use the current boolean-fix branch. The algorithm for the offset curve has been replaced by a much simpler one that does not create those nasty little self-intersections that we saw before. Also, panning has been improved to respect the zoom factor. Here is the new plunker:

http://embed.plnkr.co/jkNGoe8fD0li9DmY7u76/preview

Just activate "Merge Subpaths" and play with the handles and end points. The results are impressive, but there are still many cases that do not work. But as far as I can see, all these cases involve self-intersecting paths. On the other hand, there are already many cases with self-intersections that work.

The general problem with the new curve offset algorithm is that it can result in offset paths like this:

This has nothing to do with our boolean code. It is not nice, but not really a tragedy. Also, I have seen this problem in professional imaging software, so maybe there is no trivial way to solve it.

Anyway, this new algorithm makes it much easier to get good results. And I have the feeling that we are not too far away from a working version.

[lehni]

@iconexperience sounds very promising! Does your code life in a git repository? Would be nice to see the changes you've made, and perhaps contribute some too! I've copied the previous version locally and saw some possible code simplifications that I'd like to contribute back.

Also, for merging the sub-paths I think I have an idea that doesn't even require boolean operations. I'd like to give this a go soon, but only once your code has stabilized I guess.

[lehni]

As for the strange path, the previous code created a self intersection there, correct? Wouldn't it be better to allow these then, resolve them and filter the "islands" out?

[lehni]

What I mean is: I wouldn't necessarily try to avoid this overlapping triangle here. I would try to detect it and cut it out, because the overall outlines look cleaner and more correct than in the new code.

[lehni]

Also, since you're using the cleanUp() function which resolves self-intersection, all the failing boolean ops that are left are actual failures of the current code base, and not due to self-intersection. Would be good to extract some and create new issues for those!

[iconexperience]

@lehni
Sorry, no git repository yet. I will try to do this.
I have tried another modification to the code, which completely eliminated self intersections in the segment offsets. This improved the result again, but there were still many cases where the boolean operation failed.

Therefore I have reverted the code to the original cuve offset algorithm, which will create more issues. If the boolean operations work with this, they should have no problems with the simpler curve offset algorithm.

I think we should decide later, which algorithm to use. Let's now focus on the boolean code. I will open an new issue with some examples later today.

[kuribas]

The problem of self intersecting curves can be simply resolved by splitting the curve at vertical tangents (which is required for my algorithm). That's as simple as solving a second degree equation.

[nicholaswmin]

The _variable-stroke-expansion_ that @microbians shows here is slick, to say the least.

Is this stroke expansion via geometric path-offsetting or is it a just stroke rendering trick provided by Flash itself?

Do the approaches you guys outlined above cover such functionality(variable-stroke-expansion)? It could work wonders for Pencil Tools and sketch-like drawings.

[microbians]

@nicholaswmin Its a geometric interpolation ;) in reality it offset the quadratic bezier for the minimum and the maximun and interpolate the data in relation to ( length of the quadratic bezier segment to the subdivision point / the length of the quadratic bezier ) ~ Sorry fo the offtopic.

[lehni]

@nicholaswmin yes I am planning to support such a feature once we have constant offsetting working. Since we're dealing with cubic bezier instead of quadratic ones in Paper.js, it'll all be a wee bit more tricky, but the interpolation trick mentioned by @microbians should work similarly.

[frankrolf]

I don’t know if this is of interest, but checkOutlinesUFO (https://github.com/adobe-type-tools/afdko/blob/master/FDK/Tools/SharedData/FDKScripts/CheckOutlinesUFO.py) – which is used to remove overlaps in fonts – also uses pyClipper; inspired by Robofont.
The flattening of outlines only happens as an intermediate step, the final outlines are of course not flattened.

[benoitvb]

@iconexperience Is there a simple way to make it works for straight path as well ? For now, it brokes as my path does not contain any curve. Thanks for the help !

[kuribas]

Flattening is less efficient than bezier clipping, especially when high precision is required.

[lehni]

@iconexperience I've found some information regarding your dot product of the first and second derivative (what you called "peaks"):

http://math.stackexchange.com/questions/1954845/bezier-curvature-extrema

It looks like this simple calculation will give you something that resembles curvature extrema, but isn't quite those. I can confirm this in my tests. But finding the actual extrema is more expensive, we'd need a solver for quintic polynomials... I am wondering what we should call these peaks?

And while digging deep inside Skia's code, I found out that they do wrongly call those curvature extrema, and base their code on this assumption:

https://github.com/google/skia/blob/master/src/core/SkGeometry.cpp#L784

It's funny that this hasn't cause any issues yet. : )

[lehni]

Some more information about curvature extrema VS "peaks". I created a quick demo that compares the two methods on an interactive curve:

Demo Sketch

• Red circles are "peaks" (dot product of the first and second derivative)
• Green circles are curvature extrema (found by solving a quintic polynomial through the external poly-roots.js library for now)

This may help figuring out further which information is more useful for sub-dividing curves before performing offsetting. Perhaps we do need an internal solution to finding the actual curvature extrema?

[vcasagrande]

I've worked on a script to generate stroke outlines from a shape with line segments (non-bezier) using miter joint, I think it can be improved, but here's:

Sketch

[microbians]

Interesting doc related to WebGL + Quadratic Beziers
http://wdobbie.com/post/gpu-text-rendering-with-vector-textures/

[lehni]

Looking for further resources on Hoschek’s method after discussing different approaches with @hkrish over Skype, I accidentally came across this really curious document that describes another method for curve offsetting that claims to be much faster and as precise, if not better:

"A New Shape Control and Classification for Cubic Bézier Curves" by Shi-Nine Yang and Ming-Liang Huang: http://link.springer.com/chapter/10.1007%2F978-4-431-68456-5_17

Here the Google Books link: https://books.google.com/books?id=HJeqCAAAQBAJ&lpg=PA204&ots=YwBnF5ffia&dq=%22A%20New%20Shape%20Control%20and%20Classification%20for%20Cubic%20B%C3%A9zier%20Curves%22&pg=PA204#v=onepage&q=%22A%20New%20Shape%20Control%20and%20Classification%20for%20Cubic%20B%C3%A9zier%20Curves%22&f=false

I've extracted the pages from Google Books and turned them into a PDF for easier reading :)

A New Shape Control and Classification for Cubic Bezier Curves.pdf

I have started experimenting with this recently and the results are very promising. I will post my findings here shortly.

[lehni]

Here a first sketch that allows playing with this mentioned shape control method by dragging the green circle and all the curve handles.

[lehni]

And here finally the offsetting sketch, along with determining the largest error by projecting along the normals from the original curve, and logging plus visualization of the found largest error.

Note that this does not perform any subdivision yet, so you will naturally encounter large errors with more advanced curves. But this is yielding some really good results for "simple" curves. I will now merge this method into the code that @iconexperience has already been working on based on a different method for the offsetting part, of which much of the subdivision and path treatment can be reused.

[lehni]

I have some good news. The code is working rather beautifully in my local tests. I will put something online for people to experiment more soon, but here for now a screenshot.

[iconexperience]

That is quite a useful agorithm. In my original code I could offset through a point at t=0.5, but this one is better, as it allows for arbitrary points. I think using the point where the curve's tangent is the average of the start and end tangent could give better results than simply splitting at t=0.5.

Here is the code that I use to find points on a curve that have a certain tangent:

 /**
   * Returns the t values where the curve has a tangent in the same direction as the specified vector.
   */
getTangentTs: function (v, vTan) {
    var ax = -v[0] + 3 * v[2] - 3 * v[4] + v[6],
      bx = 3 * v[0] - 6 * v[2] + 3 * v[4],
      cx = -3 * v[0] + 3 * v[2],
      ay = -v[1] + 3 * v[3] - 3 * v[5] + v[7],
      by = 3 * v[1] - 6 * v[3] + 3 * v[5],
      cy = -3 * v[1] + 3 * v[3],
      roots = [],
      sTan,
      epsilon = paper.Numerical.CURVETIME_EPSILON;
    if (vTan.y < vTan.x) {
      sTan = vTan.y / vTan.x;
      paper.Numerical.solveQuadratic(3 * (ay - sTan * ax), 2 * (by - sTan * bx), cy - sTan * cx, roots, epsilon, 1 - epsilon);
    } else {
      sTan = vTan.x / vTan.y;
      paper.Numerical.solveQuadratic(3 * (ax - sTan * ay), 2 * (bx - sTan * by), cx - sTan * cy, roots, epsilon, 1 - epsilon);
    }
    return roots;
  };

(Update: Included epslion in getTangentTs())

[lehni]

@iconexperience I have been comparing to your original code also, and I believe that this algorithm produces the same shapes with t = 0.5! I am not 100% certain yet, but will soon put a little test-case together that allows us to easily compare these approaches. The code I linked to above also only works with t = 0.5, but based on your input I have now made a more general version of it that can work with any values of t, and will now try your suggestion. I'll put all my tests online soon, but things are behaving surprisingly well already. The trick really is to determine the maximum error and keep subdividing if it is too large.

[iconexperience]

Even more important than the maximum error is to check if one of the the handles' direction flipped during offset. If this is the case, it's is a clear sign that the result is not only unsatisfying, but quite messed up. So first check for flipping handles, then iterate until the maximum error is below you threshold.

[lehni]

That's a good point too! I've implemented their more general shape control method now that works with an arbitrary curve-time value, and was using the curve-time that has the average tangent for it, but this is producing results not as good as when using t = 0.5. But you are right, when splitting, using this "average tangent curve-time" is much better!

[lehni]

Here a useful sketch that visualizes the encountered errors:

• Orange = offset is too close
• Red = offset is too far
• magenta = offset is missing

[lehni]

And here now the status quo of the process work:

https://bl.ocks.org/lehni/raw/a665d6f9d95dd055b0ff901f8e313780/

I am very pleased by how reliable it works. The next steps are adding proper support for strokeCap and strokeJoin, and resolving self-intersections.

[lehni]

Despite the silence here I've been hard at work at getting the offsetting code work reliably. Things have far progressed, to the point where most edge-cases seem squashed, self-intersections are dealt with, and strokeJoin is already supported. Here a screenshot:

[lehni]

I am aware that this issue mainly mentions parametrized / variable width strokes. I first want to get fixed width strokes to work well, and then tackle that next. I do have some ideas as to how this algorithm can be extended to support variable width strokes.

[microbians]

Impressive work @lehni

[lehni]

Here the latest state of the offsetting code, now with boolean operations in the mix:

http://bl.ocks.org/lehni/raw/9aa7d593235f04a3915ac4cef92def02/

Unfortunately, many edge cases remain. I will compile a selection of tricky paths and give access through a pulldown menu, but please have a go and let me know your thoughts and observations.

[davelab6]

Loving it!

[BrianHanechak]

This already seems like it would be really useful in an application I'm working on, even if there are still edge cases that don't work. Is there any chance that this could be merged in soon?

[lehni]

I'm sitting on the fence about that, because it does have a lot of edge cases related to boolean operations still, and endless topic for us unfortunately... But yes, it would be great to add it soon.

[BrianHanechak]

I've tested some of the code from your demo, and it looks like it will work really well for my application.

There's a slight issue with closed paths and the joinOffsets function... basically the resulting path misses a chunk around the starting point of the input path. I can work around this by "unclosing" my path (making a new open path with an extra copy of the first point at the end.)

[lehni]

@BrianHanechak can you give an example of that problem?

[BrianHanechak]

I'm working on it but having trouble isolating it. (I'm running this inside of a much larger project). Since I'm having trouble isolating it, I'm beginning to think the problem is being caused by other things in my code.

I do get a similar issue if I pass in a compound path, which I am able to show in a fork of your gist:

https://bl.ocks.org/BrianHanechak/raw/98b0a80656c11b2a7a1a6026932298f2/

In this case, I assume it's just that compound paths aren't supported yet. But the result is similar to what I'm seeing in my bug, so I figured I'd share. I'll keep trying to track this down.

[sapics]

@lehni It's really great work!

I have a suggestion about parameter setting.
Currently, parameter (like strokeJoin) comes from the path style parameter.
I would like to set it by option (like below example), when you publish the function.

offsetPath: function(path, options){
    if(!options) options = {};
    if(options.offset == null)
        options.offset = path.getStrokeWidth() / 2;
    if(options.strokeJoin == null)
        options.strokeJoin = path.getStrokeJoin();
    if(options.miterLimit == null)
        options.miterLimit = path.getMiterLimit();
    if(options.strokeCap == null)
        options.strokeCap = path.getStrokeCap();
    ...
},

[sapics]

I found one case which looks losing some handles.
It is possible to replicate by console command in http://bl.ocks.org/lehni/raw/9aa7d593235f04a3915ac4cef92def02/.

path.pathData = "M274.01539,113.5838c-183.54286,28.92795 -238.08075,169.76149 -70.49814,239.58758c167.58261,69.82609 78.53292,249.69441 168.30932,205.80373";
$('#slider-offset').trigger('input');

[lehni]

Thanks @sapics! Yes the suggestion to optionally provide overrides for these values makes sense.

And wow, that's a funny case you found there. I am aware of a few as well, check these out:

path.pathData = "M466,467c0,0 -105,-235 0,0c-376.816,-119.63846 -469.06596,-146.09389 -650.61329,-266.59735c-282.68388,-230.49081 300.86045,-10.26825 452.77726,121.52815z";
path.pathData = "M466,467c-65,-34 136,64 0,0c-391,-270 62,-670 62,-670l-463,370z";
path.pathData = "M466,467c-65,-34 136,64 0,0c-391,-270 520,-471 522,-137c-214,-144 -1489,123 -923,-163z";

The 2nd two are linked to boolean operation issues still...

So it'll still take quite a bit of time unfortunately to get this all ready for prime-time. The question is, do we included it before?

[sapics]

These 3 cases have the similar special situations that neighbor segment.point has same position.
I am happy to use this function even if these special cases dose not fix, because it looks rare case in real use case and it might take a lot of time to fix it.
Personally, it is possible to publish or put this function to develop branch, because this function have enough practical use.
It's also possible to make a new branch (like offset-path) before publishing, it will make more reports from the participants and watchers.

path.pathData = "M274.01539,113.5838c-183.54286,28.92795 -235.08075,170.76149 -67.49814,240.58758c167.58261,69.82609 239.53292,-6.30559 329.30932,-50.19627"

This case might be without boolean operations.

[sapics]

@lehni I try to fix the case which looks losing some handles where I introduced before.
http://bl.ocks.org/sapics/raw/d10f455b8ec1e54a46cf04ed2b386334/

I cannot judge that this fix is good or bad, but, the result looks better.
You can check the difference in https://gist.github.com/sapics/d10f455b8ec1e54a46cf04ed2b386334/revisions

[microbians]

Sorry for the semi-offtopic but added variable offsetting to my shit http://microbians.com/?page=code&id=code-bezieroffsetingplayground ;)

[lehni]

@microbians not at all off topic :) Looks great! Unfortunately I haven't had any time lately to work on anything paper.js related, and that won't change for quite a while still : /

[melchiar]

Great work! This feature would be very useful in a project that I'm currently working on. Specifically, I've been looking for a way to erode/bloat a complex path. Has work on this stalled for now, or is there any chance of it being merged in the relatively near future? :)

[glenzli]

It seems this feature is still missing officially. I was design an animation editing tool and ran into this problem. I found that by the offset algorithm, there are some unwanted self-intersections. I was intend to implement same funtionalities as Adobe Illustrator's offset path and expand stroke.
I managed to cover most of the cases, and I write it as a small extend library for paper.js. I just want to share it here in case someone needs it.
The package name is paperjs-offset. It append two methods for Path & CompoundPath: offset and offsetStroke. Here is the running result of the lib.

[lehni]

@luz-alphacode this looks great! After looking at your code, I am wondering though: Did you consider using the work I posted above as a starting point? You can see it at http://bl.ocks.org/lehni/raw/9aa7d593235f04a3915ac4cef92def02/

The actual code you can see here: http://bl.ocks.org/lehni/raw/9aa7d593235f04a3915ac4cef92def02/offset.js
This includes code that handles joins and ends, through Paper's own already existing internal functions, such as Path._addBevelJoin(), Path._addSquareCap(), etc.

The offsetting code itself works really well and is based on _A New Shape Control and Classification for Cubic Bezier Curves_ by Shi-Nine Yang and Ming-Liang Huang.

The only reason why I haven't added this to paper.js yet is issues with self intersection when expanding the offset to outlines. These issues are in the boolean operations code, and I so far have not managed to find more time to try and resolve them.

Could you explain how you addressed the issues with self-intersection in your code? Can we merge these two efforts into something that can be integrated in the library officially?

[glenzli]

I've test my code again and found that my solution of finding self intersections performs reasonable for closed path but will fail on some type of open paths, and I've got some ideas about improving it. I'll check these ideas and come back later for dicussion. @lehni

...
I've tried to imporve the solution but not really successful, and it's too late in my zone and I'll try for another idea tomorrow, the issues of self-intersection detection is somehow can be related to a clockwise or counterclockwise comparision. Self-itersected path will create a a loop reverse to the direction of the original curve. But complex curves can be partial clockwise, partial counterclockwise; I think maybe I should break the curve to do it. I'll come back later to explain my idea in detail, after I get some sleep.

[melchiar]

Great to see progress on this feature! If it's of any help, I've run a few tests using the latest code from @lehni and found a bit of weirdness in certain cases where a point's handles are aligned perfectly (example below)

var pathData = "M288 216H0V44.514c21.206 0 32.848-.841 62.371-16.358C81.174 18.271 107.746 0 143.999 0c36.255 0 62.827 18.271 81.629 28.155C255.15 43.673 266.794 44.514 288 44.514V216z";

[shagarah]

Any updates / release times please?

[lehni]

@shagarah I've worked some more on it recently, but am again swamped with work currently, so can't give a timeline. I want to release this soon as part of a final v1.0.0, but it needs more tweaking to be reliable enough.

[hujiulong]

Hey guys, is there any progress on this?

[northamerican]

i can offer a financial bounty to anyone able to iron out the remaining issues with the offset code.

@lehni @glenzli @sapics

[thexperiments]

Wow I did not realize how complicated that is. Started some project with paper.js assuming this would be a nobrainer and now I‘m stuck.

What is the current status here?

Are there any workarounds via external libraries?

Thanks

[lehni]

@northamerican I should have time to start working on this again in about 6 weeks. Please get in touch at [email protected] so we can discuss this further. Thanks!

[lehni]

@northamerican did you try to get in touch? I didn't receive anything :)

[northamerican]

@lehni e-mail has been sent. ready to discuss when you are.

[martin19]

@lehni: Thanks very much for your work on this. I've got a question/comment about your offset code posted above: If I understand correctly the connect method works by connecting offset segments using the join-type set through the paths stroke style (round, bevel). Is there an exact definition on how the outline feature should work in this regard ? Is there a way to connect segments by "elongating" them and computing their intersections - this works for straight lines - I'm not sure about bezier curves? About your statement above: "These issues are in the boolean operations code" - can you give some more hints on what is going wrong? I haven't found a reference to the boolean op code in your snippet. Thanks!

[NoZ4]

I have written code for paper.js for offsetting, please find it here : https://github.com/NoZ4/paper.js-offsets
Im not good with javascript or mathamatics and its taken me 6 months to produce this. Its for procedual generation of cad designs for laser cutting

I found offsetting curves and paths are easy, its the self intersections that are the real problem along with floating point errors
so in my code I work out where self intersections will occur first and trim curves before offsetting them

Also even if curves dissapper becouse of offsetting the points where curves originally touched must be taken into account I have code creating paths along these points, with arcs.

it works with compound paths, using winding rules, so doughnut shapes can be shrunk/expandid.

I know my code has better accuracy than inkscape, i haven't tested against others.

Im quite cheery that if you expand enough the paths become a circle, or if shrunk turns into a point

it takes into account where paths totally disapper becouse they cant be offset that much and curves/paths inverseing

I got examples on github that show what i mean.

I really hope this can be of use otherwise ive wasted alot of time on nothing

[michaeltford]

Hi, first I wanted to say that I recently started using paper.js and I am amazed. I am porting a tool that renders shapes from Java to Javascript and paper.js is making this very easy. There is one problem that I am am not able to figure out.

I need to be able to render complex paths and find the bounds of these paths. It looks like I can use offset (if it's ready?) but is there a way to render double strokes or other styles? (Similar to below?).

http://www.jhlabs.com/java/java2d/strokes/

My most basic use case is to draw and capture the bounding rect of a double/triple dashed line (Similar to what PowerPoint calls a Compound Line)

https://www.officetohelp.com/powerpoint/how-to-make-compound-line-in-ppt.html

In Java2D these can be done by create a 'Brush' that walks path segments and allows for the ability to render something at each segment. (The work involved is very complicated because of rotations, miter sizes, drawing joins and all the other complicated things that people here understand better than me.

[NoZ4]

hiya,
with proper working offsets double strokes should be really easy, 5 offsets would be needid. so you have your path which would be the center of your line, you offset it + and - then you have two new lines you just need to cap off, then if you want a double line you offset the original path + or - , just more than you did before and repeat what you did for the original

dashed line should be easy just create gaps in the inital path.

brushing is something we dont have at the moment i think, but shouldnt be too hard to impliment, get even points along a path and just clone whatever you want onto that posistion.

Im currently working on my code, Im not doing double/triple line but am doing lines with variable thickness etc i'll be updating in about a week if thats any use

[michaeltford]

NoZ4. Thank you for the response. I will wait for your updates and then try to build a double/triple stroke using your technique. During my research I didn't find any JavaScript implementations of brushing. (I assume because of off the hidden complexity, google slides has an internal one they use) but paper.js seems to be very close.

I thought I would also add a picture from Powerpoint to show you the effect that I am trying to achieve.

Looking forward to trying this out!

[NoZ4]

Hiya everyone

Just thought i would give a update, my code now allows to stroke a path
example images :
https://github.com/NoZ4/paper.js-offsets/blob/master/VariableWidthstroke.SVG
https://github.com/NoZ4/paper.js-offsets/blob/master/Stroke.SVG
https://github.com/NoZ4/paper.js-offsets/blob/master/InverseStroke.SVG

theres a few known issues, shown on the page

@lehni do you think it would ever be a idea to add this to the main code? also I used a bit of your code for offsetting single curves

I think this might be a bit quicker than lehni's approach, since i got some escape early functions, but for things like square caps etc I think lehni's approach is much better.

Thanks for all the thumbs up etc before :)

Thanks everyone Noz

[northamerican]

hey, seekers of path offsets.
i have yet another option, paper-clipper to share with you. as @lehni wrote above in 2014, the Clipper library handles polygons only. however, it is very accurate in creating offsets for paths without segment handles. this library harnesses Clipper's performant boolean operations (see clipperUnite) as well as its offset functionality. it flattens Paper Paths, offsets them then applies a specialized simplify to restore curves, with good results.

with this external dependency, it isn't viable for inclusion in Paper of course but it's performant and reliable enough for my artistic uses. maybe it will come in use until we have native functionality working and approved.

if you are curious as to how it applies smoothing to the path after offsetting, refer to paper-clipper/betterSimplify.ts. it uses Paper's Path#simplify method on split up pieces of the resulting offset path. this helps retain sharper corners which simplify tends to overcompensate for.