Revision as of 10:42, 11 May 2024

Stippling is a drawing technique by which details are captured by placing points in varying densities and is frequently used in the impressionistic pointillism. This page describes a workflow to convert a digital image to a pointillism version that can be pen plotted.

Find the code on GitHub

Steps of Weighted Voronoi Stippling visualized (please, enjoy the typo)

Stochastically chosen seed points

Paths of seed points during iterative relaxation

Relaxed seed points after 50 iterations

Relaxed seed points, no background

Technique

Relaxation visualized

(bit of a placeholder, will update later)

Randomly place N seed points on your canvas
Create the Delaunay diagram for these seed points: the unique triangulation such that the no triangles circumcircle contains any points)
Create the Voronoi diagram for these seed points: polygons that represent the areas that contain all coordinates that share the seed point they're closest to. This is the dual graph of the Delaunay diagram (i.e. the vertices in the Voronoi diagram are the centers of the Delaunay circumcircles).
Apply Lloyd's Algorithm (Voronoi iteration) by iteratively moving the seed points to the centers of the Voronoi polygons. This can be approximated by the average of the polygon vertices, or better yet be calculated (see Paul Burke's reference).
Use these relaxed points for 'pointillism'

Note: for our purposes, we don't simply want to relax all points. This would ultimately lead to a uniform distribution. Instead, we want to base the relaxation on the brightness values of the image we feed in.

References

Paper introducing Weighted Voronoi Stippling
Coding Train tutorial and reference code (p5.js using D3 library)
Wikipedia: Voronoi diagram (basis for relaxation)
Wikipedia: Delaunay triangulation (dual graph to Voronoi diagram that might be used for optimized pixel-coloring)
Lloyd's Algorithm (Voronoi iteration) (way of iterative relaxation of seed points)
Calculating the center of a polygon Paul Burke's reference (not used, this script is using pixel information)

@@ Line 1: / Line 1: @@
+[https://en.wikipedia.org/wiki/Stippling Stippling] is a drawing technique by which details are captured by placing points in varying densities and is frequently used in the impressionistic [https://en.wikipedia.org/wiki/Pointillism pointillism]. This page describes a workflow to convert a digital image to a pointillism version that can be pen plotted.
+* Find the code on [https://github.com/Nyxaeroz/Plotillism GitHub]
 <center>Steps of Weighted Voronoi Stippling visualized (please, enjoy the typo)</center>
@@ Line 8: / Line 12: @@
 |}
+=Technique=
 [[File:WVS moonpool animation.gif|thumb|Relaxation visualized]]
+(bit of a placeholder, will update later)
+# Randomly place N seed points on your canvas
+# Create the [https://en.wikipedia.org/wiki/Delaunay_triangulation Delaunay diagram] for these seed points: the unique triangulation such that the no triangles circumcircle contains any points)
+# Create the [https://en.wikipedia.org/wiki/Voronoi_diagram Voronoi diagram] for these seed points: polygons that represent the areas that contain all coordinates that share the seed point they're closest to. This is the [https://en.wikipedia.org/wiki/Dual_graph dual graph] of the Delaunay diagram (i.e. the vertices in the Voronoi diagram are the centers of the Delaunay circumcircles).
+# Apply [https://en.wikipedia.org/wiki/Lloyd%27s_algorithm Lloyd's Algorithm (Voronoi iteration)] by iteratively moving the seed points to the centers of the Voronoi polygons. This can be approximated by the average of the polygon vertices, or better yet be calculated ([https://paulbourke.net/geometry/polygonmesh/ see Paul Burke's reference]).
+# Use these relaxed points for 'pointillism'
+Note: for our purposes, we don't simply want to relax all points. This would ultimately lead to a uniform distribution. Instead, we want to base the relaxation on the brightness values of the image we feed in.
-References
+=References=
 * [https://www.cs.ubc.ca/labs/imager/tr/2002/secord2002b/secord.2002b.pdf Paper introducing Weighted Voronoi Stippling]
 * [https://thecodingtrain.com/challenges/181-image-stippling Coding Train tutorial and reference code] ([https://p5js.org/ p5.js] using [https://d3js.org/ D3 library])