Hi,
I've developed an algorithm for fitting smooth curves (the curves are like in Spiro, but piecewise-linear curvature) to user sketches. I'm thinking that this could be useful in Inkscape as a replacement or alternative to the current pencil tool algorithm. Compared to existing stuff, the benefit is that the curves are usually much nicer, the drawback is that it's a complicated algorithm and is slower--fitting a curve of moderate complexity will likely take about 1 second.
Would the Inkscape devs be potentially interested in including this functionality? I'm looking into rewriting my research prototype to be faster, cleaner, more robust, and to remove proprietary dependencies. I can write the library that does the fitting, but I'm unfamiliar with Inkscape's code base, so I'd need help integrating it in. The time frame is that I'd likely be done with the library by the middle of summer.
My paper with details and comparisons to existing methods (including Inkscape) at the end is at http://www.mit.edu/~ibaran/curves/ The reported timings can probably be improved by close to a factor of 2.
Thanks,
-Ilya
On 3/31/2010 12:15 PM, Ilya Baran wrote:
I've developed an algorithm for fitting smooth curves (the curves are like in Spiro, but piecewise-linear curvature) to user sketches. I'm thinking that this could be useful in Inkscape as a replacement or alternative to the current pencil tool algorithm. Compared to existing stuff, the benefit is that the curves are usually much nicer, the drawback is that it's a complicated algorithm and is slower--fitting a curve of moderate complexity will likely take about 1 second.
Would the Inkscape devs be potentially interested in including this functionality? I'm looking into rewriting my research prototype to be faster, cleaner, more robust, and to remove proprietary dependencies. I can write the library that does the fitting, but I'm unfamiliar with Inkscape's code base, so I'd need help integrating it in. The time frame is that I'd likely be done with the library by the middle of summer.
My paper with details and comparisons to existing methods (including Inkscape) at the end is at http://www.mit.edu/~ibaran/curves/ The reported timings can probably be improved by close to a factor of 2.
Your work sounds like something that would be interesting to lib2geom too.
http://lib2geom.sourceforge.net/
Aaron Spike
Hi Ilya,
On Wed, Mar 31, 2010 at 2:15 PM, Ilya Baran <ibaran@...1007...> wrote:
Hi,
I've developed an algorithm for fitting smooth curves (the curves are like in Spiro, but piecewise-linear curvature) to user sketches. I'm thinking that this could be useful in Inkscape as a replacement or alternative to the current pencil tool algorithm. Compared to existing stuff, the benefit is that the curves are usually much nicer, the drawback is that it's a complicated algorithm and is slower--fitting a curve of moderate complexity will likely take about 1 second.
This looks very interesting, especially its ability to use linear segments and arcs where necessary. But I'm not sure such a delay would work for the interactive pen tool, even if cut by two. Pen is for fast work, sometimes many strokes per second. However, it would be very interesting to apply your algorithm for Simplify command. Do you have a parameter that allows to smoothly vary the number of nodes in the result, giving the best possible approximation for the given number of nodes?
P.S. Thank you for KSEG, one of my favorite programs of all time :)
On 03/31/2010 09:42 PM, bulia byak wrote:
This looks very interesting,
Impressive movie indeed! Now I can become an artist too ;-)
especially its ability to use linear segments and arcs where necessary. But I'm not sure such a delay would work for the interactive pen tool, even if cut by two.
Sure, but this delay probably won't be noticeable on your _next_ pc. Plus, probably it can be taken care of by those idle cores. The only real use I have found for them so far is in compiling Inkscape!
I'd vote for making it toggleable in the pen tool, but it's all up to the one who picks up the glove.
Diederik
On Wed, 2010-03-31 at 21:57 +0200, Diederik van Lierop wrote:
On 03/31/2010 09:42 PM, bulia byak wrote:
This looks very interesting,
Impressive movie indeed! Now I can become an artist too ;-)
especially its ability to use linear segments and arcs where necessary. But I'm not sure such a delay would work for the interactive pen tool, even if cut by two.
Sure, but this delay probably won't be noticeable on your _next_ pc. Plus, probably it can be taken care of by those idle cores. The only real use I have found for them so far is in compiling Inkscape!
I'd vote for making it toggleable in the pen tool, but it's all up to the one who picks up the glove.
I agree with you on this... given that we selectively have multi-core support for gaussian blur, it would be nice if we could do the same for other newly-introduced code (if could be done safely).
Cheers, Josh
Wow, that's very nice, Ilya. I really like the oversketching, too. All the best with integrating this into Inkscape (sorry, can't offer any useful tips here since I'm not really an Inkscape developer)
Sure, but this delay probably won't be noticeable on your _next_ pc.
Not intending to start a flamewar or anything, but it may be noticeable on _somebody else's_ next pc ;-) I don't think any effort spent optimizing (after a working implementation, of course) would be wasted.
- Bryan
-- Bryan Hoyt, Web Development Manager -- Brush Technology Ph: +64 3 942 7833 Mobile: +64 21 238 7955 Web: brush.co.nz
Hi, Bulia,
This looks very interesting, especially its ability to use linear segments and arcs where necessary. But I'm not sure such a delay would work for the interactive pen tool, even if cut by two. Pen is for fast work, sometimes many strokes per second.
The strokes in the paper are somewhat more complicated than what a non-Chuck-Norris artist would be able to draw in one second. For quick strokes that are well-approximated by three or fewer segments, the current implementation has a delay of about 0.2 seconds. I am not an artist, so I don't know if such a delay is acceptable.
However, it would be very interesting to apply your algorithm for Simplify command. Do you have a parameter that allows to smoothly vary the number of nodes in the result, giving the best possible approximation for the given number of nodes?
I currently have a tradeoff parameter that determines how important simplicity is versus accuracy, but I can binary search on it to turn it into a hard constraint on the number of segments (at a performance cost that I can't predict without running tests).
P.S. Thank you for KSEG, one of my favorite programs of all time :)
Glad you like it--but it's overdue for an overhaul, on my extensive todo list :)
Thanks,
-Ilya
On Wed, Mar 31, 2010 at 5:21 PM, Ilya Baran <ibaran@...1007...> wrote:
The strokes in the paper are somewhat more complicated than what a non-Chuck-Norris artist would be able to draw in one second. For quick strokes that are well-approximated by three or fewer segments, the current implementation has a delay of about 0.2 seconds. I am not an artist, so I don't know if such a delay is acceptable.
Well, let's just try it then :) As I remember it's just a single function call from pen-context.cpp to run the fitting. You just need to adapt your algorithm to use our path representation structure (currently it's lib2geom almost everywhere) and you will have no problems plugging it in.
I currently have a tradeoff parameter that determines how important simplicity is versus accuracy, but I can binary search on it to turn it into a hard constraint on the number of segments (at a performance cost that I can't predict without running tests).
Actually we don't have a guarantee of a number of nodes in our current simplify algorithm either, and it often happens than a slight simplify produces more nodes than before. So it would be unfair to request this guarantee from you :) However, you need some way to estimate, given an arbitrary path, how high should the tradeoff parameter to be in order to make the result simpler (less nodes) in a reasonable majority of cases.
-----Original Message----- From: Ilya Baran [mailto:ibaran@...1007...] Sent: woensdag 31 maart 2010 19:16 To: inkscape-devel@lists.sourceforge.net Subject: [Inkscape-devel] Curve Sketching
Hi,
I've developed an algorithm for fitting smooth curves (the curves are like in Spiro, but piecewise-linear curvature) to user sketches. I'm thinking that this could be useful in Inkscape as a replacement or alternative to the current pencil tool algorithm. Compared to existing stuff, the benefit is that the curves are usually much nicer, the drawback is that it's a complicated algorithm and is slower--fitting a curve of moderate complexity will likely take about 1 second.
Would the Inkscape devs be potentially interested in including this functionality? I'm looking into rewriting my research prototype to be faster, cleaner, more robust, and to remove proprietary dependencies.
Are you familiar with alt+pencil tool sketching? http://wiki.inkscape.org/wiki/index.php/Release_notes/0.47#Pencil_sketch_mod... The idea was to be able to roughly sketch a shape, then release the alt button and have Inkscape "trace" the sketch for a smooth shape. Perhaps your work could be the key in doing this :)
I haven't got the time right now to look at your demo, but it sounds very interesting!
Like Aaron wrote, it may be interesting for lib2geom too. Be sure to send a mail to us on the lib2geom maillist :P
Ciao, Johan
cheers, Johan
Hi, Johan,
Are you familiar with alt+pencil tool sketching? http://wiki.inkscape.org/wiki/index.php/Release_notes/0.47#Pencil_sketch_mod... The idea was to be able to roughly sketch a shape, then release the alt button and have Inkscape "trace" the sketch for a smooth shape. Perhaps your work could be the key in doing this :)
I haven't seen it before, but it makes sense--using oversketching to refine a curve is natural for artists. I think it should be possible to improve the result quality using my algorithm, but it's not completely obvious what the right interaction is. I don't think Alt+pencil currently gets it quite right (e.g., oversketching starting from the middle of a curve moves the beginning instead of editing just the part that's oversketched), but there's a lot of potential. These guys: http://www.dgp.toronto.edu/~shbae/ilovesketch.htm have an interesting take--watch their sketching from the first minute of the video.
I haven't got the time right now to look at your demo, but it sounds very interesting!
Like Aaron wrote, it may be interesting for lib2geom too. Be sure to send a mail to us on the lib2geom maillist :P
At this point it sounds like there's definitely enough interest for me to proceed. I think I'll start a discussion with the lib2geom folks when I have some code to show :)
Thanks,
-Ilya
On 4/1/10, Ilya Baran wrote:
Hi, Johan,
Are you familiar with alt+pencil tool sketching? http://wiki.inkscape.org/wiki/index.php/Release_notes/0.47#Pencil_sketch_mod... The idea was to be able to roughly sketch a shape, then release the alt button and have Inkscape "trace" the sketch for a smooth shape. Perhaps your work could be the key in doing this :)
I haven't seen it before, but it makes sense--using oversketching to refine a curve is natural for artists. I think it should be possible to improve the result quality using my algorithm, but it's not completely obvious what the right interaction is. I don't think Alt+pencil currently gets it quite right (e.g., oversketching starting from the middle of a curve moves the beginning instead of editing just the part that's oversketched), but there's a lot of potential. These guys: http://www.dgp.toronto.edu/~shbae/ilovesketch.htm have an interesting take--watch their sketching from the first minute of the video.
As a matter of fact, ILoveSketch is where Johan got this idea from and adapted to Inkscape :)
Alexandre
participants (8)
-
unknown＠example.com -
Aaron Spike -
Alexandre Prokoudine -
Bryan Hoyt | Brush Technology -
bulia byak -
Diederik van Lierop -
Ilya Baran -
Joshua A. Andler