Enclose and fill tool

This is a proposal for a new filling tool based on the tool of the same name present in Clip Studio Paint. All this text is kind of an analysis of that tool and an attempt to recreate it, but that doesn't mean I think it should be a copy of CSP or that there can't be better ways of achieving the same results.

1. What does it do?

This tool can be used to fill irregular regions, just like the normal fill tool. The main difference is on how the users select the region that needs to be filled.

Basically the users have to draw an enclosing region around the closed regions they want to be filled. If a closed region is partially outside the enclosing region, it is not filled.

Clearly, if the users only want to fill a small number of relatively medium or big size regions, they can rely on the classic bucket fill. But if they want to fill small, hard to click on, regions, or fill a bunch of disconnected regions at once, this tool can be of great help.

Figure 1. Typical enclose and fill usecase. The closed regions that lie entirely inside the enclosing region are filled.

Figure 2. More specific enclose and fill usecase. The closed regions that lie entirely inside the enclosing region and that are surrounded by black are filled.

2. How to make the enclosing region?

At the end, the enclosing region is just a mask, so there are a lot of ways it could be created. The ones that come to my mind and I think are more useful are similar to the selection tools: lasso, polygon, rectangle, ellipse, brush.

I propose having at least three ways of creating the region:

• Lasso. This would allow making an irregular region with the pointer, just like the lasso selection tool. It could make sense to mix the polygonal way with this one.
• Rectangle. One can argue that it is just a polygon, but this allows to create an enclosing region just by moving the pointer in a straight line, and can be faster in some situations. I think the ellipse way is not as useful, since it is similar to the rectangle and I have the feeling it would be better than the rectangle only for surrounding elliptical shapes.
• Brush. This allows creating the region just by painting. It allows creating regions that the other ways can't. For example it could create a ring-like mask, allowing to fill later only that ring and not the interior region.

The main problem here I think is how to handle the subtool selection. Would it be better to have a single enclose and fill tool with different submodes? Or would it be better to have entirely different tools, one for each enclosing region creation mode (like the selection tools)?

Figure 3. Different ways of making the enclosing region and the fills they produce.

3. What to include in the fill?

I think it's better to first define what a closed region is in the context of this text. It is a connected area in the image. An area such that if you perform a flood fill operation on one of its pixels, it is totally filled. Of course this depends on the colors of the pixels in the area, but also on an optional threshold value which is used to meassure a difference between colors.

If a closed region is partially outside of the enclosing region it is not taken into account when filling. Since the users didn't totally surround it, it problably means they didn't want it to be filled.

For example, in figure 1, the long, vertical, triangle-like shape that points down in the middle, along with the bottom blob it intersects, form 4 closed regions (following our previous definition). Three of them are the white regions inside the strokes, and the other one is the stroke itself (even if it apperars to be two strokes, one for each shape, since they were drawn in the same layer they became connected and now form one unique closed region). So the only one of those four regions that lies entirely inside the enclosing region is the tiny white region on the intersection of the two shapes. On the other hand, the other shapes that are filled in the same figure have both the interior and the stroke inside the enclosing region, so both regions, white and black, are filled.

Now, there will be times when the users will want to finetune what regions are selected for filling. For example, imagine we have a layer with black lineart and transparent background. Then we want to fill only the enclosed regions that are transparent, keeping the black lines untouched. The basic approach will fill every closed region, including regions that are not transparent, like black lines if there are some segments that lie entirely inside the enclosing region, or the regions that were already painted. For this case, it is useful to specify what color should be painted, in this case transparent. Then between all the selected closed regions only those which are transparent would be filled.

At other times, the users will want to fill any closed region, no matter its color, as long as they are surrounded by a specific color. For example, filling the regions between black lines, no matter the color of the region, but excluding the black lines themselves even if they constitute a closed region inside the enclosing region.

CSP provides some predefined and hard coded ways of selecting which regions should be filled. For Krita, I propose letting the users choosing which color should the closed regions have as well as the color of the surrounding region. Although CSP doesn't allow mixing the two, I think it should be possible, for example, to "fill closed transparent regions surrounded by black", or other combinations. I would let the users choose between these options (for both the regions to fill and the surounding region):

• Any color
• Transparent
• White
• White or transparent
• Black
• Black or transparent
• Custom color

Transparent, white and black (and combinations of those) are just shortcuts for the most common colors that, in my opinion, would be used by the users, and they could be set also using a custom color.

4. Possible implementation

In the following, I explain what I deduced from playing with CSP's demo and its enclose and fill tool. All the images in this text were created with Krita using the fill tool and the contiguous selection tool, trying to replicate the algorithm.

The parameters that the user can modify in the GUI are basicaly the same as the ones on the fill tool, with some additions:

• Widgets to set the color of the closed regions we want to select.
• widgets to set the color that the surrounding region to the regions we want to select must have.
• If there is only one enclose and fill tool then the enclosing method is implemented as an "enclosing mode" option.

From my point of view, what the tool does can be separated in very selfcontained stages, and it uses very simple primitives like flood filling and mask boolean operations.

In the examples used in this section the region color selected to fill is transparent.

4.1. Defining the enclosing region

4.1.1. Inputs

The input of this stage is the pointer input itself.

4.1.2. Output

The output is a mask created from the pointer input that defines the enclosing region.

4.1.3. Observations

Depending on the type of subtool, the mask can be created at the end of the input stream, from the set of points (lasso rectangle), or as it goes (brush).

Figure 4. An enclosing mask is created from the user input.

4.2. Getting the regions to fill

4.2.1. Inputs

• The mask that represents the enclosing region.
• A reference paint device with the pixels that will be used to guide the flood filling.
• The color of the regions on the reference paint device we want to fill.
• A threshold value used to determine if pixels are similar enough to the previous color to be included in the fill region.
• The color of the region surrounding the regions we want to fill.
• A boolean that tells if the current selection should be used as boundary.

4.2.2. Output

A mask that represents the regions that need to be filled.

4.2.3. Implementation

This stage can take one of two different paths depending on the color selected for the surroundings of the closed regions.

The first step is common and consists on intersecting the enclosing mask with the current selection if the option is set to true.

The second step is also common and consists on getting the set of all points that are at the boundary of the enclosing mask. For this it helps that the mask is aliased, binary.

We also create a new mask that will be used to identify the regions that should be filled.

4.2.3.1. Get closed regions surrounded by any color

• Perform several flood fills using the boundary points as seeds and the reference paint device to sample the pixels. Then use the masks obtained by each flood fill to paint the newly created mask. The flood fills should nor extend outside the enclosing region.
  
  This step may seem very expensive but the mallority of the flood fills will return early if we check if the seed point is already filled on the new mask.
  
  Some important issue is finding a threshold value for flooding that works well in most cases.
  
  
  
  Figure 5. The mask that defines the non closed regions inside the enclosing mask, generated by flood filling along its contour.

• Now we have a mask that represents all the regions inside the enclosing mask that should not be filled, so we have to invert it and intersect it with the enclosing mask since just inverting will select the region outside the enclosing mask as well as the closed regions inside it.
  
  
  
  Figure 6. The mask that defines the closed regions inside the enclosing mask.

• Now we finally have a mask that represents all the closed regions inside the enclosing mask. The last step is to subtract from that mask all the regions that are not similar to the chosen color. To meassure the similarity we use the threshold value.
  
  
  
  Figure 7. The mask that defines the final regions used for filling. In the example we only want to fill the transparent regions, so those are the only ones remaining. If we would choose "any color" option, instead of a specific one, then the final mask would be equal to the one in the previous step.

4.2.3.2. Get closed regions surrounded by a specific color

For this we need to implement a new distance policy to be used in the flood fill algorithm. Such policy will select all the colors as long as they are not similar to a reference color. It is kind of the opposite to the classic flood fill. The classic approach is to keep flooding as long as the neighbor pixels are similar to the reference color (usually the color at the seed point). This new method needs to keep flooding as long as the neighbor pixels are not similar to the reference color.

In this example we use black as the surround color.

Supposing we wave that new way of flood filling we have to follow these steps:

• Perform several of the new flood fills using the boundary points as seeds and the reference paint device to sample the pixels. Also the surround color should be passed to the flood fills as reference so they know when to stop the flooding. Then use the masks obtained by each flood fill to paint the newly created mask.
  
  
  
  Figure 8. The mask that defines the non closed regions inside the enclosing mask, excluding the blar regions, generated by flood filling along its contour up to the black regions.

• Now we have a mask that represents all the regions inside the enclosing mask that clearly should not be filled, so we have to invert it and intersect it with the enclosing mask since just inverting will select the region outside the enclosing mask as well as the closed regions inside it.
  
  
  
  Figure 9. The mask that defines the closed regions inside the enclosing mask plus the black regions.

• Now we finally have a mask that represents all the closed regions inside the enclosing mask that are surrounded by the surround color as well as the regions that constitute the surrounding regions themselves. The last step is to subtract from that mask all the regions that are not similar to the chosen color as well as all the regions that are considered surrounding (regions with color similar to the surround color chosen). To meassure the similarity we use the threshold value.
  
  
  
  Figure 10. The mask that defines the final regions used for filling. In the example we only want to fill the transparent regions that are surrounded by black, so those are the only ones remaining. If we would choose "any color" option, instead of a specific one, then the final mask would also include the white region in the intersection of the two big blobs at the top.

4.3. Postprocessing

4.3.1. Inputs

• The mask that represents the regions that need to be filled.
• A growth value used to expand/contract the mask.
• A feathering value used to blur the mask.

4.3.2. Output

The mask that represents the regions that need to be filled, but modified by growth and feathering values.

4.4. Filling

4.4.1. Inputs

• A mask that represents the regions that need to be filled, posibly modified.
• A boolean that tells if the regions should be filled with a pattern.
• Pattern options.

4.4.2. Outputs

None.

4.4.3. Observations

The mask is used to fill the current layer, with the current color or pattern.