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 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.

[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 notifications@github.com 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 < notifications@github.com> 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.