Paint Bucket: geometric, not perceptual mode

Bug #170588 reported by Bug Importer on 2005-02-15
48
This bug affects 6 people
Affects Status Importance Assigned to Milestone
Inkscape
Wishlist
Unassigned

Bug Description

A bucket fill tool that generates a vector object with
the desired color. It should be useful with the use of
the dinamic brush so a designer could make the black
lines and paint the blank spaces with this tool.

Bug Importer (bug-importer) wrote :

I would like to see this feature added as well.

Here's what it would do:

1 render image into a temporary arena bitmap;

2 apply bucket fill algorithm from gimp;

3 trace the result by potrace to create path

Bug Importer (bug-importer) wrote :

I think it would be better to think of it as a shape
creation tool, based on the discernable edges. That way, you
may be able to incrementally select more, adding elements
together to create your shape. Once the shape is made, it's
easy to color it - best to separate these two operations I
think.

Philhibbs (philhibbs) wrote :

I don't think that rasterizing the image is the way to go.
What resolution do you use? It will always be just
approximate. Also it should take note of white lines, lines
that are so thin that they don't get rendered to the bitmap,
and black lines that have white shapes over them.

Rasterizing is imprecise, but it's the only sensible way to
do this. Any other way will be unable to e.g. fill into
white areas of bitmaps and gradients, which would make it
much less useful. As for white lines, why SHOULD this tool
stop at them? On the contrary, I think it should treat these
lines exactly as the human eye treats them, i.e. not notice
them. That's the idea and the value of this tool: It does
what you _expect_ by filling in empty space that you _see_
as empty (even if in fact it has some white, transparent or
hidden stuff).

The resolution to use? Maybe dynamically adjusted depending
on zoom, maybe just fixed high enough to cover all possible
zooms. We'll see what is best.

Erich-users (erich-users) wrote :

The bug you merged with,
https://sourceforge.net/tracker/?func=detail&atid=604309&aid=1275286&group_id=93438
contains lots of information.

Using rasterization is a bad bad bad idea. DONT.

Instead do whats proposed in the bug above - use set operations.
Just cut the active layers (you can make white lines
inactive if you want to) with a big box, then delete every
generated chunk of the big box except the one the user would
have clicked upon. This gives you a nice path object.

Using rasterization is exactly what makes this idea
workable, attractive, innovative and universally useful.
This is my opinion, and I'm going to go ahead with it. You
are free to do your own booleans-based tool and let the
users decide which is better.

Just imagine, for example, using this tool to selectively
trace bitmaps. Just click on someone's t-shirt in a photo
and you get at once a vector path tracing this t-shirt and
nothing else. So much faster and more convenient than
regular tracing, and your booleans-based tool will never be
able to do this at all.

As for which resolution to use, of course this should be the
current screen resolution. So if you don't get enough
detail, just undo, zoom in and fill again to get more
precision. Very natural.

Erich-users (erich-users) wrote :

Of course you can rasterize and then go through all the pain
of vectorizing it again. But why would you?
In fact many people prefer to _manuall_ trace outlines on an
image because they aren't happy with automatic tracing.

But why would you, when Inkscape *ALREADY HAS* everything
you need to do it exactly?
(see earlier comments for a step-by-step howto on it)

> Of course you can rasterize and then go through all the pain
of vectorizing it again. But why would you?

Because going through bitmap allows us to do away with
limitations and complications of the path-based approach and
to do filling based on what the user actually SEES, which
will always be much more intuitive. This has distinct
advantages not only for bitmaps and gradients, but later
also for filters such as gaussian blur or procedural fills,
multiple fills/strokes for one object (SVG 1.2 feature) etc.
etc. In a word, this method is universal and intuitive,
whereas the method of combining boolops is limited and often
will give unexpected results.

And by the way, boolean ops are NOT exact. They almost
always introduce small distortions.

> In fact many people prefer to _manuall_ trace outlines on an
image because they aren't happy with automatic tracing.

Different users have different needs. Some need precision,
others need freedom, natural feel, and convenience. My tool
is best for creative drawing, not technical. And if
technical users need the more precise boolop-based
path-limited version of this tool, anyone is welcome to
develop it. It might be a different mode of the same bucket
fill tool, or it can be a separate tool. So we don't
actually need to argue - Inkscape can be everything for
everyone :)

Kulhas (kulhas) wrote :

- I would use a mix of the two methods like this:
  - first i find the vector region to paint,
then i would find if there is a bitmap in that region, if
there is first thing would be potrace the bitmap
, then intersect the two regions and add color to it.

There is no need to potrace all bitmap , only the region to
paint.
And there should be a option to ignore the bitmap.

Digulla (digulla) wrote :

kulhas: Why treat bitmaps differently from normal vectors?

*: As for rasterize and trace, here is an idea: Don't trace.
Instead overlay the vector image and the fill. Now, scan
every line and search for transitions (nonfill->fill and
fill->nonfill).

Select all paths which are close to these transitions.

Copy them.

Iterate over all intersections and cut the paths there so
you get a bunch of free paths.

Do the transition selection again

Delete all non-selected paths

Now, you should have the outline of the fill as a path with
a pretty good precision.

TODO: When doing the raster fill, how do we handle
non-closed forms? Do we clip at the view borders? Document
borders? At the bounding box of all elements?

Kulhas (kulhas) wrote :

digulla:

 I think thats not the way because you have allways to
potrace the bitmap region to fill, because you have to find
the vector shape that defines the fill of bitmap. So we must
use potrace to find the best vector shape that defines the
bitmap border to fill.

If you try to fill a shape by aproximation you may end up with
a shape that doesnt exactly fit in the paint region, but if
we only work with vectors we can get exactly the correct
fill region, dont forget that we should be able to zoom the
image without loosing information.

> When doing the raster fill, how do we handle
> non-closed forms?

I think that we should first find the paint region, if there
is other non-closed forms included in our paint region we
should put this forms in a layer above of the paint region
layer.This will make it more fast because we will have less
points to calculate. And more easy to the user to manipulate
the paint region.

Digulla (digulla) wrote :

> I think thats not the way because you have allways to
> potrace the bitmap region to fill, because you have to
> find the vector shape that defines the fill of bitmap.

Why? With my idea, we're just using the bitmap (without
tracing it) to find the vectors which make up the outline of
the fill (the transition points in the bitmap tell us where
to look for the elements of the outline).

But if you insist in a poly-only solution: First, we try to
find an intersection with the outline (send a ray to the
right, select closest intersection). This is point A.

Now, determine all intersections of this object with all others.

Go to the closest intersection (point B). Add the path from
A to B to result.

Determine which side of the intersecting element points
"away". Make the intersection to point A. Repeat.

If, at any stage, you cannot find intersections on the
correct side of A, the outline is not closed.

At this point, we might want to find the closest element and
check if the minimal distance is below a certain (user
specified) limit. If so, we create a line segment between
the two closest points and add that to the result.

If not, we abort with an error. We can even move the view to
the point were we couldn't continue so the user can fill the
gap and retry.

To determine whether to go left or right at an intersection,
this code might be useful:
http://www.alienryderflex.com/polygon/

There is also an example which works with splines.

Kulhas (kulhas) wrote :

I think the problem in here is not to find the vector region
to paint , but to handle bitmaps.

You can see very easy if a vector shape is open or closed.
If you are inside of a region you know that is closed shape,
if you are not in a region then in most formats you have a
flag to know if the shape is open or closed, if is open (
then its open ) , if its closed you need to know if you are
in the region or not , there is a few methods to do this (
one is your method ).

we do this detection in all shapes until we have a closed
region to paint!

Handle bitmaps :

Your method seems to me thats doing the potrace job in
bitmaps, so why dup code ?? well this is just my openion!!

Digulla (digulla) wrote :

> Your method seems to me thats doing the potrace job in
> bitmaps, so why dup code ??

Because my method uses the exact outline. After tracing the
bitmap with potrace, the outline will be quite different,
depending on the zoom, the pixel size of the bitmap, etc.

My method is using the transition points is independent of
the resolution and it will always create an exact copy of
the outline.

Bug Importer (bug-importer) wrote :

If using boolean-ish operations, surely the curve points
derived from the existing shapes could be somehow ID'd and
attached to the original curves? That way the fill could
adapt to stay as a fill?

I really hate the raster/trace option, it just seems like a
solution that someone thinks is "good enough" to trick the
eye in most cases.

Sure, booleans can be a little inexact, but addressing that
could be part of the bucket project :)

Philhibbs (philhibbs) wrote :

Q: What does Inkscape do?
A: Creates .svg files.

Q: What does the "s" in "svg" stand for?
A: Scalable.

It isn't a paint pakage; any feature that is restricted to
the current resolution of the screen really goes agaist the
fundamental concept of Inkscape in my opinion.

Nobody said:
>Sure, booleans can be a little inexact, but addressing that
>could be part of the bucket project :)

In the name of exactness, I would even go so far as to say
that the intersection of the new shape with the existing
shapes should create new nodes in the existing shapes in
order to ensure an exact fit. I.E. Where two shapes
intersect, add a node in each one at the intersection. If
there are multiple lines in multiple shapes (e.g. a circle
and a band around the circle), then add the node to all
coincident lines. Maybe a tick box in the fill creation
dialog box to enable this option, as it will be slower and
will have a wider impact on the drawing.

Phil Hibbs
Technical Consultant
Capgemini

Digulla (digulla) wrote :

> Why not use the points of the original curves?

Because not all points of the original curves become part of
the new path which simulates the bucket fill.

The main problem we face is to determine if any point on any
curve is part of the outline of the bucket fill or not.

Cloning it after determining that it is is tricky because
"is on the outline" can be changed by moving the original point.

Also, we face another problem: Will people expect the bucket
fill to become independent of the limiting curves after the
operation completes? Or will they expect this to be a
"permanent operation" in the sense that changine the curves
which limit it will trigger a re-fill.

Maybe we could fake the operation and achieve something
which works with much less effort:

1. User selects "Create Outline Path" tool
2. User can now pick path segments. A path segment is the
part of the path between two intersections and/or an
end-point of the path
3. Selecting a path segment again deselects it
4. When the user has selected all path segments he wants, he
finishes the operation.
5. Inkscape will now create a new path made up from all the
path segments.

If there are gaps, Inkscape will either create a group of
independent paths or it will fill the gaps in the order in
which the user selected the segments.

Lastly, the user can choose to close the path (if it isn't
already) and fill it.

For most shapes, creating a fill should only take a few
mouse-clicks with this kind of tool.

Originator: NO

Current SVN has a paint bucket tool that uses the tracing-bitmap approach.
Note: using this approach was a free choice of the author of the tool. He
was aware of both approaches and chose this one. He's an artist drawing
comics so this approach was better for him.

Of course nothing prevents someone from implementing the geometric mode in
the same tool. So I'm not closing this RFE but renaming it. Here's the
possible algorithm for geometric paintbucket:

* when the user clicked on canvas, make a list of all objects on the
current layer

* exclude from the list those object(s) that are under click point

* compute bbox of all the objects in the list

* union the copies of all objects (converting to paths if necessary)

* create a rect the size of the bbox

* subtract the union from the rect

* inset the result by the tolerance parameter (no inset if tolerance=0)

* break apart

* examine all the objects that resulted from breaking apart and remove
those that are not under click point; this leaves a single path

* outset the result by the tolerance parameter (no outset if tolerance=0)

* add the result to the document.

Ryan Lerch (ryanlerch) on 2007-12-07
Changed in inkscape:
importance: Undecided → Wishlist
status: New → In Progress
su_v (suv-lp) wrote :

Changing bug status back to 'Triaged' (comment #19) because there has been no further activity since the status had been changed to 'In Progress' three years ago.

Changed in inkscape:
status: In Progress → Triaged
Andrei Nacu (andreinacu1) wrote :

Is there any chance of seeing a geometric-fill bounded area tool in the coming future?

I am using Inkscape to draw maps and I find this tool a top necessity. The current tool is not suitable at all for topologically accurate drawings!

I came up with a workaround to get a bucket tool like the one described in the title of this bug report:
https://www.youtube.com/watch?v=XeFgXKzCOlQ

It's not perfect but it does the job.
is this what you are talking about in this bug report. I got confused when somebody wrote something about resterization. My reply to that is NO. Please, no. Raster logic is the reason the current bucket tool leaves too much clean up work.

not that I hope to see any progress on a wish reported 9 years ago :P

John P (johnpharrell) wrote :

For what it's worth, I would like to see this being implemented. It's the only reason keeping me from switching to Inkscape completely. From a professional point of view, a vector that has gaps in the fill is just hideous when it comes to print finishes.

John P (johnpharrell) wrote :

Guess people may as well use Microsoft Paint. It's just as accurate as far as bitmap paint bucket fill goes...

Bert Van de Poel (bhack) wrote :

I think this bug is very weird. If I for example have a large double edged path with a "hole" in the middle and I want to fill it with the fill tool, that there is no way to have it actually fill the hole. This makes little sense, since a filler vector could be easily deduced. I'm quite confused why this bug is stale.

To post a comment you must log in.
This report contains Public information  Edit
Everyone can see this information.

Duplicates of this bug

Other bug subscribers