[gimp-web-devel/pat/bootstrap] content: add Line Art Bucket Fill algorithm description.

[Jehan <jehanp src gnome org>]

commit 6595428fa80f358b68b66117e8885cc0be916f48
Author: Jehan <jehan girinstud io>
Date:   Wed Sep 7 17:13:16 2022 +0200

    content: add Line Art Bucket Fill algorithm description.
    
    The other algorithm felt quite lonely! So I quickly wrote up the Line
    Art algorithm (hopefully I didn't make mistakes or forgot points or
    change, as it's been a few years now!). It's also useful to have this
    here.

 content/core/algorithm/line-art-bucket-fill.md | 243 +++++++++++++++++++++++++
 1 file changed, 243 insertions(+)
---
diff --git a/content/core/algorithm/line-art-bucket-fill.md b/content/core/algorithm/line-art-bucket-fill.md
new file mode 100644
index 0000000..1e26166
--- /dev/null
+++ b/content/core/algorithm/line-art-bucket-fill.md
@@ -0,0 +1,243 @@
+---
+title: "Line Art Bucket Fill"
+Author: "Aryeom and Jehan"
+Date: 2022-09-07
+---
+
+The "*Fill by line art detection*" option in the Bucket Fill tool is
+adapted from an algorithm named "[A Fast and Efficient Semi-guided
+Algorithm for Flat Coloring
+Line-arts](https://hal.archives-ouvertes.fr/hal-01891876)" by Sébastian
+Fourey, David Tschumperlé and David Revoy.
+
+I (Jehan) implemented it as a new option in the "Bucket fill tool", as a
+job for the
+[CNRS](https://en.wikipedia.org/wiki/French_National_Centre_for_Scientific_Research)
+research center, under direction of David Tschumperlé and Sébastian
+Fourey.
+
+Aryeom was the principal artist advisor for all the changes and
+improvements we made to the algorithm, but also to improve user
+experience and graphical interface.
+
+This page is not going to re-explain the algorithm in details, but
+instead will try to simplify the algorithm flow, break it into clear
+steps and explain changes we did for our implementation.
+
+## Algorithm intent
+
+This is not a generic bucket fill algorithm, in that it won't work with
+any random image. It is really dedicated to "line art" drawing, or any
+image which can be usefully pre-processed into a line art looking image.
+Hence the name of the feature.
+
+In particular, chances are that running it on a photography won't give
+you very useful result.
+
+The advantages of this algorithm for such line art images are in
+particular:
+
+* Unlike other bucket fill algorithms which usually rely on color
+  proximity, by detecting what "lines" are, we detect the borders of
+  fill zones, and that makes it easier to "flood" the fill color or
+  pattern under the lines. This prevents the very common issue of thin
+  ugly unfilled pixels near line borders (because of antialiased pixels
+  for instance) which makes other bucket fill algorithms unusable in
+  practice for many simple-looking cases.
+* Line art zones are not always perfectly closed. In some occasions, it
+  is just some imperfect lines due to the nature of drawing. In other
+  cases, it is even on purpose, as a line art style, where you don't
+  want to close our strokes even though they might represent closed
+  areas. The algorithm is meant to try and detect when such unclosed
+  areas should have been.
+
+## 3-steps algorithm
+
+There are basically 3 steps performed during a line art bucket fill:
+
+1. Detect what is line art.
+2. "Guess" what are line art which are supposed to be closed and try to
+   create closures.
+3. Fill the enclosed area and flood under the line art.
+
+### Step 1: line art detection
+
+The first step is a very basic conversion of the image into a single
+channel, using a threshold to decide whether a pixel is part of a line
+or not.
+
+This channel can either be based on luminosity (light means background),
+i.e. grayscaling the image, or just using the alpha channel (if "*Detect
+opacity rather than grayscale*" is checked and there is an alpha
+channel).
+
+In the end, we get a binarized version of the images with some pixels
+belonging to strokes, and others not. This step is fast and easy.
+
+### Step 2: line art closure
+
+The second step is the most important part of the algorithm, and the
+best is to look at the research paper linked earlier. Basically from the
+binarized image, we are trying to characterize key points, which are
+supposed to be "extremities" of strokes. This is done by computing
+local normals and curvatures at each stroke point.
+
+Once we have keypoints, the algorithm proposes closures based on
+keypoints proximity. The closure can take the form of splines (curved
+closure) or segments (straight lines). The original algorithm has 2
+variables to determine whether we consider a closure of any type
+(`spline_max_length` and `segment_max_length`). This is implemented in
+GIMP core code, but not shown in the <abbr title="Graphical User
+Interface">GUI</abbr> as the Bucket Fill tool options only displays a
+single "*Maximum gap length*" which is used for both variables. This was
+chosen for simplification of usage.
+
+#### Improvement over the research paper
+
+A first improvement in our implementation, unlike the research paper, is
+that the original algorithm (as published) was not working fine on fat
+strokes because it was using a global median stroke thicknes. It even
+ended up opening holes in line art in some cases. To work whatever the
+stroke size, we needed to compute a **local** radius estimate for every
+stroke border point. It is more accurate and less processing intensive.
+
+The [commit implementing this
+change](https://gitlab.gnome.org/GNOME/gimp/-/commit/b00037b8500bee6ba7fcf1082c8c4c707fdfb1bc)
+has more details on the change, information on what alternatives were
+evoked and the actual implementation.
+
+#### Usage warning
+
+Note that this algorithm will work better with smooth strokes. When
+drawing lines using a brush with obvious "texture", such as the
+"Acrylic" collection of brushes in default GIMP brush set, the rough
+characteristic of the lines end up creating more keypoints than it
+should (i.e. not only in extremities, yet also in middle of strokes). It
+may make this step slower and create too many closed zones. No absolute
+solution for this issue has been found.
+
+### Step 3: filling closed area and flooding (line art) borders
+
+The actual bucket fill step, where you intended to go, is different in
+the research paper and our implementation.
+
+The first reason is because the original authors envisioned a "all area
+at once" workflow where an artist give all colors for the whole image,
+using color spots, and let the algorithm choose the zones to fill.
+Instead we stay on a workflow assuming you want to work on a specific
+zone only with a single color.
+[Originally](https://gitlab.gnome.org/GNOME/gimp/-/commit/8502b4e7431761c487107ffd49022b2ccd3585ff)
+we were using the `"gegl:watershed-transform"` GEGL operation.
+
+Eventually we [moved to a simpler and much faster
+algorithm](https://gitlab.gnome.org/GNOME/gimp/-/commit/3467acf096fab265d55e2882b91b870da5db975b)
+based on a distance map and a local thickness map, in order to flood at
+most half of the stroke (depending on local radius at each point). This
+made the border flooding very efficient.
+
+This is another major difference from the originally proposed algorithm
+in the research paper.
+
+## GUI enhancements
+### Line art pre-computation
+
+The line art computation can take some time, in particular for big and
+complex images. This is not really the first step, but especially the
+second step (characterizing key points and closing) which can be the
+most expensive.
+
+As a consequence, we made these 2 steps [work in a
+thread](https://gitlab.gnome.org/GNOME/gimp/-/commit/a3cda4abbe229ad5d4d512122c5089d2a77f7ba0).
+As soon as the tool is selected or as soon as the source image is
+modified, computation starts (and not when you click on canvas with the
+tool). Since a few microseconds may pass between several clicks, it
+allows a sensation of instantness as all the harder processing happened
+in this in-between time.
+
+### Holding the pointer while filling
+
+A second GUI enhancement is that as long as you don't release your
+pointer, the line art and closure are not recomputed and simply reused,
+allowing you to "refine" your fill. It makes it faster, and also allows
+you to cancel a fill by right-clicking (third button) when releasing.
+
+### Line art source
+
+We also added a concept of line art "source". Typically the source for
+the line art can be the selected layer itself, but also the whole image
+("Sample merged" equivalent) or the layer above or below, depending on
+whether you want to fill using the source transparency (common use case
+for fully digitally-drawn pictures) or often with "*Multiply*" mode too
+(common use case for working based on cleaned-up scans).
+
+This is not only useful to cater to various workflows but also because
+any source where the filled image is not a part of (i.e. when the source
+is "*Layer above the selected one*" or "*Layer below the selected one*")
+will be lightning fast as the line art and closure will never have to be
+recomputed.
+
+### Disabling second step
+
+Another <abbr title="User eXperience">UX</abbr> improvement was the
+ability to disable the second step of the algorithm (line art closure)
+by unchecking the "*Automatic closure*" option.
+
+The base idea is that:
+
+1. In some conditions, as explained above, too many key points are
+   created and closures become an annoyance more than anything else.
+2. For many drawing styles, unclosed line arts are not expected (or
+   should be fixed).
+
+Therefore it made sense to allow disabling the closure creation
+algorithm as this is the costlier (in processing time). Note that
+setting "*Maximum gap length*" to 0 is equivalent, but having a checkbox
+was a lot simpler and better experience (you don't lose your ideal gap
+length setting, in case you need to regularly switch from one fill style
+to another).
+
+### Using target merged to source (manual closure)
+
+Also there exist methods to create closures manually, which are used by
+advanced artists, such as Aryeom, who often teach it to university
+students.
+
+The base idea is that other fill or selection algorithm per color
+proximity are "leaking" through line art holes. Yet sometimes you just
+don't want to close the hole because it's on purpose, as an unfinished
+stroke style. How do you close without closing?
+
+In this case, what you can do is to close the hole… with your fill color
+and style (on the fill layer, not the line art layer). Then color
+distance computed in sample merged mode will close the line art. Of
+course, there is still the problem of the thin unfilled zone near stroke
+borders. This is why colorists would use the "*Fuzzy Select*" tool
+instead, then grow the selection and finally fill it.
+
+Here is what Aryeom would do (note that she had scripts to do it in much
+fewer steps, but this is what the low-level steps are actually doing):
+
+1. Line art is top (or bottom) layer, and color is bottom (resp. top)
+   layer. A closed area is represented but the line style doesn't
+   actually close the area. Let's say the line color is black while fill
+   color is blue.
+2. Select the color layer, and close the unclosed area with the fill
+   color (blue) and a paint tool.
+3. Switch to the "Fuzzy select" tool, in "Sample merged" and "Select by
+   Composite". Click inside the area (which is now closed since we are
+   in sample merged mode so both the line and color layers are taken
+   into account).
+4. Grow the selection by a few pixel (`Select > Grow` in menus) as
+   needed, depending on the approximate line size. This will simulate
+   our flooding step.
+5. Switch to "Bucket fill" tool in "Fill whole selection" and fill with
+   fill color (blue).
+
+This whole procedure can be reproduced now with the Bucket fill tool in
+"Fill by line art detection", unchecking "Automatic closure" and
+checking "Manual closure in fill layer" instead.
+
+It will then merge a binarized version of the fill layer to the line
+layer, the same way as it's done in the first step. The only difference
+is that no closure are computed from the fill layer, so it stays fast
+even though this part has to be re-computed after each change.