Access to the wiki to add a better bucket tool design proposal
Hello everyone! There was a google+ discussion where I expressed thought on a better bucket tool implementation and discussed issues with the current one. https://plus.google.com/u/0/+inkscape/posts/4ZGgz6XKmGo As a result +Martin Owens https://plus.google.com/102241005050666075649 and +Tavmjong Bah https://plus.google.com/111969650498055377139 invited me to this mailing list to get involved in the effort to improve the bucket tool in inkscape.
I need to write a proper design proposal at inkscape's wiki. In it I plan to outline the workflow issues and include examples of better bucket fill implementations from other open source software and public algorithms / research papers . How do I go about getting write access to the wiki page and where do I exactly file my proposal?
Thank you in advance for the time.
Best regards, Todor
Hi !
I experienced a few "bucket deceptions" when I started, and took a look at how things are done (not that i could do better myself, but i wanted to know how things work), so here are some thoughts:
The current bucket tool[1] works by: -> creating a rasterized image of the screen -> "fill" the adjacent pixels that have ~ the same color as the pixel you clicked on, with a quite simple algorithm (that may be improved) -> vectorize the resulting bunch of pixels with potrace, and simplify the result, creating another path on top of the image.
This probably can be improved or done differently, of course, but the current version has some points to keep in mind: it "works" on vector parts, including overlapping ones, but also on bitmap parts, or on anything, vector or not, allowing people to use it to quickly and simply "vectorize" parts of anything with it.
For a while now I'm only using it when i have no choice and on raster parts ( = almost never. And I don't miss it ! In 99% of the cases when people i know ask me for help there is no need for bucket[and in some cases, it is as simple as "select the object, change its fill. Why did you want to use the bucket, did you think this was MSPaint ? --the "object fill" paradigm is not obvious for people coming from the raster world that see the existence of a bucket like-the-one-they-know-but-not-quite-the-same -- ]). When it's vector I always find a way to use path operations to get something more satisfying.
There could potentially be a way to do things "the vector way" automatizing what can be done with path operations, but doing something that would work with potentially mixes of gradients, patterns, masking, filters, texts, and so on, without going through a pixel representation can be tricky. And if you want to fill "the pixel way" there will always be the question of what zoom to go, what level of precision you want, in the rendering AND in the tracing, etc. Maybe the two approaches can be mixed in some way (first pixel-based, then looking for vector segments that already exist and would seem to be on the tracing edge ... or vectorization done at the same time as the "filling" and not with potrace afterwards... just random thoughts here.) You mentionned toonboom's vector bucket in g+, but a quick google search only gave me a store page with something at $1200 and probably closed-source...
Anyway, I'll wait for your proposal: I have convinced myself for some time that "paint bucket is inherently a raster tool" but if I'm proved wrong and an awesome vector bucket tool gets implemented in inkscape, or if the tool is hugely improved in some way, all the better :)
I wrote a wiki page about it here: http://wiki.inkscape.org/wiki/index.php/A_better_Bucket_Fill_tool_fill
Let me know what you guys think! :)
On Sun, Apr 26, 2015 at 3:53 AM, Marc Jeanmougin <marc@...3062...> wrote:
Hi !
I experienced a few "bucket deceptions" when I started, and took a look at how things are done (not that i could do better myself, but i wanted to know how things work), so here are some thoughts:
The current bucket tool[1] works by: -> creating a rasterized image of the screen -> "fill" the adjacent pixels that have ~ the same color as the pixel you clicked on, with a quite simple algorithm (that may be improved) -> vectorize the resulting bunch of pixels with potrace, and simplify the result, creating another path on top of the image.
This probably can be improved or done differently, of course, but the current version has some points to keep in mind: it "works" on vector parts, including overlapping ones, but also on bitmap parts, or on anything, vector or not, allowing people to use it to quickly and simply "vectorize" parts of anything with it.
For a while now I'm only using it when i have no choice and on raster parts ( = almost never. And I don't miss it ! In 99% of the cases when people i know ask me for help there is no need for bucket[and in some cases, it is as simple as "select the object, change its fill. Why did you want to use the bucket, did you think this was MSPaint ? --the "object fill" paradigm is not obvious for people coming from the raster world that see the existence of a bucket like-the-one-they-know-but-not-quite-the-same -- ]). When it's vector I always find a way to use path operations to get something more satisfying.
There could potentially be a way to do things "the vector way" automatizing what can be done with path operations, but doing something that would work with potentially mixes of gradients, patterns, masking, filters, texts, and so on, without going through a pixel representation can be tricky. And if you want to fill "the pixel way" there will always be the question of what zoom to go, what level of precision you want, in the rendering AND in the tracing, etc. Maybe the two approaches can be mixed in some way (first pixel-based, then looking for vector segments that already exist and would seem to be on the tracing edge ... or vectorization done at the same time as the "filling" and not with potrace afterwards... just random thoughts here.) You mentionned toonboom's vector bucket in g+, but a quick google search only gave me a store page with something at $1200 and probably closed-source...
Anyway, I'll wait for your proposal: I have convinced myself for some time that "paint bucket is inherently a raster tool" but if I'm proved wrong and an awesome vector bucket tool gets implemented in inkscape, or if the tool is hugely improved in some way, all the better :)
-- Mc
[1] http://bazaar.launchpad.net/~inkscape.dev/inkscape/trunk/view/head:/src/ui/t...
----- Mail original ----- De: "Todor Imreorov" <blurymind@...400...> À: inkscape-devel@lists.sourceforge.net Envoyé: Dimanche 26 Avril 2015 00:36:09 Objet: [Inkscape-devel] Access to the wiki to add a better bucket tool design proposal
Hello everyone! There was a google+ discussion where I expressed thought on a better bucket tool implementation and discussed issues with the current one. https://plus.google.com/u/0/+inkscape/posts/4ZGgz6XKmGo
As a result + Martin Owens and + Tavmjong Bah invited me to this mailing list to get involved in the effort to improve the bucket tool in inkscape.
I need to write a proper design proposal at inkscape's wiki. In it I plan to outline the workflow issues and include examples of better bucket fill implementations from other open source software and public algorithms / research papers . How do I go about getting write access to the wiki page and where do I exactly file my proposal?
Thank you in advance for the time.
Best regards, Todor
Great proyect!
El 26 de abril de 2015 06:55:28 EDT, Todor Imreorov <blurymind@...400...> escribió:
I wrote a wiki page about it here: http://wiki.inkscape.org/wiki/index.php/A_better_Bucket_Fill_tool_fill
Let me know what you guys think! :)
On Sun, Apr 26, 2015 at 3:53 AM, Marc Jeanmougin <marc@...3062...> wrote:
Hi !
I experienced a few "bucket deceptions" when I started, and took a
look at
how things are done (not that i could do better myself, but i wanted
to
know how things work), so here are some thoughts:
The current bucket tool[1] works by: -> creating a rasterized image of the screen -> "fill" the adjacent pixels that have ~ the same color as the pixel
you
clicked on, with a quite simple algorithm (that may be improved) -> vectorize the resulting bunch of pixels with potrace, and simplify
the
result, creating another path on top of the image.
This probably can be improved or done differently, of course, but the current version has some points to keep in mind: it "works" on vector parts, including overlapping ones, but also on bitmap parts, or on anything, vector or not, allowing people to use it to quickly and
simply
"vectorize" parts of anything with it.
For a while now I'm only using it when i have no choice and on raster parts ( = almost never. And I don't miss it ! In 99% of the cases
when
people i know ask me for help there is no need for bucket[and in some cases, it is as simple as "select the object, change its fill. Why
did you
want to use the bucket, did you think this was MSPaint ? --the
"object
fill" paradigm is not obvious for people coming from the raster world
that
see the existence of a bucket
like-the-one-they-know-but-not-quite-the-same
-- ]). When it's vector I always find a way to use path operations to
get
something more satisfying.
There could potentially be a way to do things "the vector way" automatizing what can be done with path operations, but doing
something
that would work with potentially mixes of gradients, patterns,
masking,
filters, texts, and so on, without going through a pixel
representation can
be tricky. And if you want to fill "the pixel way" there will always
be the
question of what zoom to go, what level of precision you want, in the rendering AND in the tracing, etc. Maybe the two approaches can be
mixed in
some way (first pixel-based, then looking for vector segments that
already
exist and would seem to be on the tracing edge ... or vectorization
done at
the same time as the "filling" and not with potrace afterwards...
just
random thoughts here.) You mentionned toonboom's vector bucket in g+,
but a
quick google search only gave me a store page with something at $1200
and
probably closed-source...
Anyway, I'll wait for your proposal: I have convinced myself for some
time
that "paint bucket is inherently a raster tool" but if I'm proved
wrong and
an awesome vector bucket tool gets implemented in inkscape, or if the
tool
is hugely improved in some way, all the better :)
-- Mc
[1]
http://bazaar.launchpad.net/~inkscape.dev/inkscape/trunk/view/head:/src/ui/t...
----- Mail original ----- De: "Todor Imreorov" <blurymind@...400...> À: inkscape-devel@lists.sourceforge.net Envoyé: Dimanche 26 Avril 2015 00:36:09 Objet: [Inkscape-devel] Access to the wiki to add a better bucket
tool
design proposal
Hello everyone! There was a google+ discussion where I expressed thought on a better bucket tool implementation and discussed issues with the current one. https://plus.google.com/u/0/+inkscape/posts/4ZGgz6XKmGo
As a result + Martin Owens and + Tavmjong Bah invited me to this
mailing
list to get involved in the effort to improve the bucket tool in
inkscape.
I need to write a proper design proposal at inkscape's wiki. In it I
plan
to outline the workflow issues and include examples of better bucket
fill
implementations from other open source software and public algorithms
/
research papers . How do I go about getting write access to the wiki page and where do
I
exactly file my proposal?
Thank you in advance for the time.
Best regards, Todor
One dashboard for servers and applications across Physical-Virtual-Cloud Widest out-of-the-box monitoring support with 50+ applications Performance metrics, stats and reports that give you Actionable Insights Deep dive visibility with transaction tracing using APM Insight. http://ad.doubleclick.net/ddm/clk/290420510;117567292;y
Inkscape-devel mailing list Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel
On Sun, 2015-04-26 at 13:55 +0300, Todor Imreorov wrote:
I wrote a wiki page about it here: http://wiki.inkscape.org/wiki/index.php/A_better_Bucket_Fill_tool_fill
Thanks for putting this page together.
Let me know what you guys think! :)
This might be a good project for our new funded development model.
Tav
Hi Todor, a great project; though very challenging!
I think we can extend Krysztof's boolops work to handle bucketfill, here's how:
Bucketfill is actually computing the connected components of a graph defined by the rendered colour, but this graph is not made from pixels, but the imaginary infinite resolution pixels we use with vector graphics.
So we need a representation that can increase in resolution until we can define the border exactly. In this representation we need to perform these operations:
1) Find me the region that is the same as the tip point
2) Find me the neighbouring regions that match my bucket fill sameness function. for traditional bucket fill this is exact match, but you might want to use magic wand style tolerance, or foreground extraction with graph cut as per your links.
3) Merge regions.
Pixels are very convenient for this because you only have to sample for 1), consider the four or eight neighbours for 2) and maintain a border set of pixels for 3). Converting to pixel representation is already implemented by the screen rendering code.
But pixels are quantised, and the rasteriser hides information by averaing within each pixel.
If we could store all the pieces used to make the pixel for each pixel then we could re-raster any pixels we were unsure of. If all the pieces affecting a specific single pixel covered it completely we can actually compute an exact description of the fill region in that shape and either merge it or not.
So this gives a recursive algorithm: somehow rasterise the image at a low resolution, but modifying the rasteriser to flag all the pixels that are edge.
Some downsides: modifying the rasteriser is not trivial (as mentioned recently), perhaps you can store undecisive pixels in a separate channel, but you're going to have to touch every part of the code. Instead, I think you might be able to handle most cases by rendering an image using the wireframe mode - draw the outlines of fill regions, and the stroke outlines and these pixels are most of your edge candidates. You'll also have to work out gradient contours and bitmap contours, which are easy when combined with solid fills. But when you have multiple bitmaps or gradients with alpha interacting you're solving simultaneous equations. Those cases will probably just have to be rendered to bitmap and filled the old way. But it sounds plausible.
The second problem is that it somewhat inefficient - most vector graphics has only a small number (<10000) of elements, but this would generate millions of intermediate elements even for a single circle.
Instead, use a recursive representation to reduce to only considering border pixel regions - 1) is done with repeated rasterisation, 2) is a bit more fiddly, but is essentially a tree traversal, and 3) is again managing a set of border patches.
Both of these methods will generate a lot of nodes for non axis aligned edges. You're going to have to zoom in a long way to make potrace recover the exact contour.
But if each pixel/quad knows which contour(s) defines it, we can use the new boolops to reassemble back into a single shape. To do this, when we paint the contour map we can use a different colour for each element and if we turn off antialiasing and we are sure there is only one edge in our sample pixel we can simply read back the colour that was drawn and know which coresponding vector element generated it.
It seems like it would be even better to just stay in a vector-graph representation, but although 1) is straightforward, 2) and 3) seem as hard as boolops to implement, and even harder to incorporate gradients and bitmaps.
njh
On Sun, Apr 26, 2015 at 01:55:28PM +0300, Todor Imreorov wrote:
I wrote a wiki page about it here: http://wiki.inkscape.org/wiki/index.php/A_better_Bucket_Fill_tool_fill
Let me know what you guys think! :)
On Sun, Apr 26, 2015 at 3:53 AM, Marc Jeanmougin <marc@...3062...> wrote:
Hi !
I experienced a few "bucket deceptions" when I started, and took a look at how things are done (not that i could do better myself, but i wanted to know how things work), so here are some thoughts:
The current bucket tool[1] works by: -> creating a rasterized image of the screen -> "fill" the adjacent pixels that have ~ the same color as the pixel you clicked on, with a quite simple algorithm (that may be improved) -> vectorize the resulting bunch of pixels with potrace, and simplify the result, creating another path on top of the image.
This probably can be improved or done differently, of course, but the current version has some points to keep in mind: it "works" on vector parts, including overlapping ones, but also on bitmap parts, or on anything, vector or not, allowing people to use it to quickly and simply "vectorize" parts of anything with it.
For a while now I'm only using it when i have no choice and on raster parts ( = almost never. And I don't miss it ! In 99% of the cases when people i know ask me for help there is no need for bucket[and in some cases, it is as simple as "select the object, change its fill. Why did you want to use the bucket, did you think this was MSPaint ? --the "object fill" paradigm is not obvious for people coming from the raster world that see the existence of a bucket like-the-one-they-know-but-not-quite-the-same -- ]). When it's vector I always find a way to use path operations to get something more satisfying.
There could potentially be a way to do things "the vector way" automatizing what can be done with path operations, but doing something that would work with potentially mixes of gradients, patterns, masking, filters, texts, and so on, without going through a pixel representation can be tricky. And if you want to fill "the pixel way" there will always be the question of what zoom to go, what level of precision you want, in the rendering AND in the tracing, etc. Maybe the two approaches can be mixed in some way (first pixel-based, then looking for vector segments that already exist and would seem to be on the tracing edge ... or vectorization done at the same time as the "filling" and not with potrace afterwards... just random thoughts here.) You mentionned toonboom's vector bucket in g+, but a quick google search only gave me a store page with something at $1200 and probably closed-source...
Anyway, I'll wait for your proposal: I have convinced myself for some time that "paint bucket is inherently a raster tool" but if I'm proved wrong and an awesome vector bucket tool gets implemented in inkscape, or if the tool is hugely improved in some way, all the better :)
-- Mc
[1] http://bazaar.launchpad.net/~inkscape.dev/inkscape/trunk/view/head:/src/ui/t...
----- Mail original ----- De: "Todor Imreorov" <blurymind@...400...> À: inkscape-devel@lists.sourceforge.net Envoyé: Dimanche 26 Avril 2015 00:36:09 Objet: [Inkscape-devel] Access to the wiki to add a better bucket tool design proposal
Hello everyone! There was a google+ discussion where I expressed thought on a better bucket tool implementation and discussed issues with the current one. https://plus.google.com/u/0/+inkscape/posts/4ZGgz6XKmGo
As a result + Martin Owens and + Tavmjong Bah invited me to this mailing list to get involved in the effort to improve the bucket tool in inkscape.
I need to write a proper design proposal at inkscape's wiki. In it I plan to outline the workflow issues and include examples of better bucket fill implementations from other open source software and public algorithms / research papers . How do I go about getting write access to the wiki page and where do I exactly file my proposal?
Thank you in advance for the time.
Best regards, Todor
One dashboard for servers and applications across Physical-Virtual-Cloud Widest out-of-the-box monitoring support with 50+ applications Performance metrics, stats and reports that give you Actionable Insights Deep dive visibility with transaction tracing using APM Insight. http://ad.doubleclick.net/ddm/clk/290420510;117567292;y
Inkscape-devel mailing list Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Done, you should have an e-mail from our wiki in your inbox.
2015-04-25 18:36 GMT-04:00 Todor Imreorov <blurymind@...400...>:
Hello everyone! There was a google+ discussion where I expressed thought on a better bucket tool implementation and discussed issues with the current one. https://plus.google.com/u/0/+inkscape/posts/4ZGgz6XKmGo As a result +Martin Owens and +Tavmjong Bah invited me to this mailing list to get involved in the effort to improve the bucket tool in inkscape.
I need to write a proper design proposal at inkscape's wiki. In it I plan to outline the workflow issues and include examples of better bucket fill implementations from other open source software and public algorithms / research papers . How do I go about getting write access to the wiki page and where do I exactly file my proposal?
Thank you in advance for the time.
Best regards, Todor
One dashboard for servers and applications across Physical-Virtual-Cloud Widest out-of-the-box monitoring support with 50+ applications Performance metrics, stats and reports that give you Actionable Insights Deep dive visibility with transaction tracing using APM Insight. http://ad.doubleclick.net/ddm/clk/290420510;117567292;y _______________________________________________ Inkscape-devel mailing list Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel
participants (6)
-
Jabier Arraiza -
Krzysztof Kosiński -
Marc Jeanmougin -
Nathan Hurst -
Tavmjong Bah -
Todor Imreorov