Algorithm Design

Algorithm Design #

This page provides an in-depth exploration of the algorithms utilized by this add-on, both for developers interested in vector graphics processing and for users wondering about the core principles underlying the add-on’s functionality.

It is less recommended to read the source code directly, since the code details are not excellent and still need refinement. Instead, this article focuses more on the mathematics behind each feature.

The add-on’s functions fall into two categories:

  • The first category comprises classical algorithms and I simply deploy third-party Python packages to perform them. For these functions, this page lists the names of the packages and the main algorithms for reference.
  • The second category consists of methods developed by myself learning mainly from academic projects. The documentation describes the main steps of each method and the research papers I used as inspiration.
Since this is not a formal academic publication, for some well-known concepts I will cite Wikipedia pages as the source for convenience.

Polygon Operations #

The polygon operations (Boolean, offset and sweep) are performed by directly adopting the Clipper library without my own design. Several classic algorithms are implemented in Clipper:

  • Boolean operations are achieved by the Vatti clipping algorithm[1].
  • Hole detection and offset are achieved by computing winding numbers[2].
  • Sweep operation is achieved by using Minkowski addition[3].
  1. Vatti, Bala R. "A generic solution to polygon clipping." Communications of the ACM 35, no. 7 (1992): 56-63.
  2. Chen, Xiaorui, and Sara McMains. "Polygon offsetting by computing winding numbers." In International Design Engineering Technical Conferences and Computers and Information in Engineering Conference, vol. 4739, pp. 565-575. 2005.
  3. https://en.wikipedia.org/wiki/Minkowski_addition

Sketch Cleanup #

The purpose of sketch cleanup is to merge multiple 2D strokes with the similar shape into a single, smooth one. It looks like a curve fitting problem, but it is not trivial to solve:

  • It is common that the input strokes cannot be represented by a function \(y=f(x)\) since a single \(x\) may correspond to multiple \(y\) values.
  • Modeling input strokes as \left{\begin{matrix} y=f(t) \ x=g(t) \end{matrix}\right. is also problematic, because it is hard to determine the parameter \(t\) (i.e., the order of input points) among multiple input strokes.

The method adopted here is to treat the input strokes as a set of unordered 2D points and then construct a curve from them. I refer to two research papers[1][2] which share several common steps:

  1. Perform Delaunay triangulation[3] on all input points and treat the result as a graph.
  2. Calculate the minimum spanning tree (MST)[4] of this graph.
  3. Find the longest path between any two nodes in MST.

These steps lead to a 2D path which is the output stroke, but it is usually not smooth enough. The two research papers have different ways further processing the stroke. Considering the time complexity, however, a distinct method is developed for this add-on:

  1. For each point in the calculated longest path, find other input points (that do not belong to the path) in the neighborhood given a radius value. Average their coordinate of the normal direction.
  2. Perform a B-spline fitting using SciPy to get the final result.
Multiple input strokes to fit.
Triangulation from the input point set.
Get MST from the triangles.
Get the longest path from MST.
Smooth the longest path to get the final result.
  1. Lee, In-Kwon. "Curve reconstruction from unorganized points." Computer aided geometric design 17, no. 2 (2000): 161-177.
  2. Liu, Chenxi, Enrique Rosales, and Alla Sheffer. "Strokeaggregator: Consolidating raw sketches into artist-intended curve drawings." ACM Transactions on Graphics (TOG) 37, no. 4 (2018): 1-15.
  3. https://en.wikipedia.org/wiki/Delaunay_triangulation
  4. https://en.wikipedia.org/wiki/Minimum_spanning_tree

Smart Fill #

LazyBrush[1] is a tool that allows users to fill a line art based on some hint colors drawn on it. It is originally designed to process pixels of a raster image. This add-on adopts the concept of LazyBrush, but modifies the algorithm to make it work for vector arts.

The key idea is the max-flow min-cut theorem[2]. The min-cut partitions a graph into two disjoint subsets. We use it to partition the points of the line art, and assign a color to each output subset, which is how the line art is filled.

The way of constructing a node graph from the vector line art is inspired by the research paper Delaunay Painting[3]. The add-on performs Delaunay triangulation on the line art stroke points, and builds a graph with triangles as graph nodes. For each pair of adjacent triangles (sharing an edge):

  • If the edge belongs to the line art, do not create a link between the two graph nodes.
  • Otherwise, create a weighted link. The weight is the length of the edge.

The max-flow min-cut method requires source and sink nodes, which are triangles with two different hint colors. With the min-cut disconnecting source nodes from sink nodes, the graph is partitioned into two, which are the filling areas of these two colors. If there are \(N>2\) hint colors, just repeat this process for \(N-1\) times.

The description above may be obscure since many details of the graph theory have to be involved. The figures below aim at providing an intuitive example about how this method works.

Input line art and hint strokes.
Divide the line art into triangles.
Convert triangles to a node graph.
Partition the graph into two parts.
Fill each subgraph with one color.
  1. Sýkora, Daniel, John Dingliana, and Steven Collins. "Lazybrush: Flexible painting tool for hand‐drawn cartoons." In Computer Graphics Forum, vol. 28, no. 2, pp. 599-608. Oxford, UK: Blackwell Publishing Ltd, 2009.
  2. https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem
  3. Parakkat, Amal Dev, Pooran Memari, and Marie‐Paule Cani. "Delaunay Painting: Perceptual Image Colouring from Raster Contours with Gaps." In Computer Graphics Forum, vol. 41, no. 6, pp. 166-181. 2022.

Mesh Generation #

Among different mesh generation operators, the Offset/Frustum method uses the same algorithm as the polygon offset, while the normal interpolation method is based on a different principle.

Normal Vector Interpolation #

This method aims at generating continuous normal vectors on a 2D surface to create an effect of depth and 2D lighting. Research projects such as Lumo[1] have proposed to adopt this method to create shading for hand-drawn animation.

The algorithm starts with a Grease Pencil stroke, which can be seen as the contour of a 2D shape. Supposing the contour contains \(C\) points, \(\{(x_1, y_1), (x_2, y_2), ..., (x_C, y_C)\}\) , it is easy to get their 2D normal vectors \( \{(n_{1x}, n_{1y}), (n_{2x}, n_{2y}), ..., (n_{Cx}, n_{Cy})\} \) . We then normalize them to the unit length and treat them as 3D vectors, assuming that the third dimension has zero value, i.e., assuming the vector is parallel to the 2D work plane.

Calculated 2D normal vectors from stroke points.
Add new vertices inside the stroke shape.
Each new vertex's normal vector is a weighted average of all contour normal vectors.

Then we create new vertices inside the shape. To calculate the normal vector of such an inside vertex, we take the weighted average of the normal vectors of all the contour points. The weight is the reciprocal squared distance from this new vertex to a contour point.

n_x = \frac{ \sum_{c=1}^{C} [(x-x_c)^2 + (y-y_c)^2]^{-1} n_{cx}}{\sum_{c=1}^{C} [(x-x_c)^2 + (y-y_c)^2]^{-1}}

n_y = \frac{ \sum_{c=1}^{C} [(x-x_c)^2 + (y-y_c)^2]^{-1} n_{cy}}{\sum_{c=1}^{C} [(x-x_c)^2 + (y-y_c)^2]^{-1}}

The equations above give us the first two components of the normal vector. By assuming the unit length, we can get the third component:

n_z = \sqrt{1 - {n_x}^2 - {n_y}^2}

This distance-based weighting and averaging can result in a smooth appearance. For example, a 2D circle will be shaded like a sphere.

Height/Depth Calculation #

A normal map can be converted to height/depth values to get an actual 3D mesh. This add-on implements an inflation method by modifying a pixel-based algorithm[2] to a vector-based one.

The method is based on the fact that the normal vector should always be perpendicular to the tangent vector. The tangent vector of a vertex \(a\) can be calculated by subtracting its coordinates from those of another vertex \(b \in \Gamma_{a}\) that shares an edge with it. In this way, an energy function can be defined by summing up the squared production of each pair of normal and tangent vectors, taking each edge in the mesh into account:

E(z_1, z_2, ..., z_N) = \sum_{a=1}^N \sum_{b\in \Gamma_{a}} (\begin{bmatrix} n_{ax} & n_{ay} & n_{az} \end{bmatrix} \begin{bmatrix} x_a - x_b \ y_a - y_b \ z_a - z_b \end{bmatrix})^2

The closer this energy is to zero, the more realistic the depth values are. Since the derivative of energy is linear, there is a wide range of optimizers available for this problem. The add-on adopts the L-BFGS-B algorithm provided by SciPy.

Although not using its algorithm directly, the mesh generation module is also largely inspired by Monster Mash[3].

2D Shading #

This add-on also supports calculating shadows and lights directly as vector polygons instead of generating 3D meshes. Similar concepts have also been discussed in some research papers. Unlike the research[4] which proposes a novel formula to determine the shadow terminator, this add-on simply reuses the same method of normal interpolation combined with Boolean operations. However, my implementation benefits from certain techniques suggested by this research, such as sampling along the direction of the light.

  1. Johnston, Scott F. "Lumo: illumination for cel animation." In Proceedings of the 2nd international symposium on Non-photorealistic animation and rendering, pp. 45-ff. 2002.
  2. Hudon, Matis, Sebastian Lutz, Rafael Pagés, and Aljosa Smolic. "Augmenting hand-drawn art with global illumination effects through surface inflation." In Proceedings of the 16th ACM SIGGRAPH European Conference on Visual Media Production, pp. 1-9. 2019.
  3. Dvorožňák, Marek, Daniel Sýkora, Cassidy Curtis, Brian Curless, Olga Sorkine-Hornung, and David Salesin. "Monster mash: a single-view approach to casual 3D modeling and animation." ACM Transactions on Graphics (TOG) 39, no. 6 (2020): 1-12.
  4. Hudon, Matis, Rafael Pagés, Mairéad Grogan, Jan Ondřej, and Aljoša Smolić. "2D shading for cel animation." In Proceedings of the Joint Symposium on Computational Aesthetics and Sketch-Based Interfaces and Modeling and Non-Photorealistic Animation and Rendering, pp. 1-12. 2018.

Image Vectorization #

The image vectorization operators (including line art extraction and color quantization) are mostly performed by directly calling functions of SciPy and Scikit-Image modules.

Line Art Extraction #

The algorithm used for extracting lines from raster image pixels belongs to skeletonization or thinning. There have been several famous methods[1,2] developed for this purpose. This add-on chooses medial_axis implemented in skimage.morphology, since it calculates the distance from a pixel to the extracted skeleton, which is later converted to the radius of Grease Pencil stroke points.

Color Quantization #

To vectorize a color image, the add-on uses the clustering algorithm to reduce the number of colors of the original image, so that pixels of each color can be treated one by one, just like a black-and-white image. The clustering algorithm in use is a very common one, K-means[3], treating each pixel's rgb values as a 3D vector.

After color reduction, the add-on converts each connected pixel regions to a contour by calling the function find_contours in skimage.measure, which uses the marching squares algorithm[4].

  1. Skimage Skeletonize, https://scikit-image.org/docs/stable/auto_examples/edges/plot_skeleton.html
  2. Zhang, Tongjie Y., and Ching Y. Suen. "A fast parallel algorithm for thinning digital patterns." Communications of the ACM 27, no. 3 (1984): 236-239.
  3. K-means Clustering, https://en.wikipedia.org/wiki/K-means_clustering
  4. Lorensen, William E., and Harvey E. Cline. "Marching cubes: A high resolution 3D surface construction algorithm." In Seminal graphics: pioneering efforts that shaped the field, pp. 347-353. 1998.

File Format Support #

The support of Adobe formats (writing .psd and reading .abr) follows the official specification[1]. In addition, the parsing of brush files also refers to the description from Just Solve the File Format Problem[2] Wiki page and GIMP's source code[3].

The support of GIMP .gbr brushes follows the developer documentation[4].

A Procreate brush is an archive with image files and PLIST configurations. A Clip Studio Paint .sut brush is an SQLite database. Both formats can be parsed by the Python Standard Library.

  1. Adobe Photoshop File Format Specification, https://www.adobe.com/devnet-apps/photoshop/fileformatashtml/
  2. Just Solve the File Format Problem, http://fileformats.archiveteam.org/wiki/Photoshop_brush
  3. https://github.com/GNOME/gimp/blob/master/app/core/gimpbrush-load.c
  4. The GIMP Paintbrush File Format, https://github.com/GNOME/gimp/blob/gimp-2-10/devel-docs/gbr.txt