Stippling describes the pattern by which shades of varying intensities are simulated using small dots. Darker shades are represented by densely packed dots, lighter ones by more sparse dots.
While there are many methods of recreating the stippling effect from an image in computer graphics, I found one that was particularly interesting because it uses a particle based approach. The original paper can be read here.
The simulation operates on two layers: The sample layer and the deposit layer.
Sample Layer
In the sample layer we have the particles which will constitute the final image; they are constrained to a 2D plane. All the particles are electrically charged, and have the same charge value Qs.
We simulate the electro-static forces acting on our particles, and because they all have the same charge, they will repel one another until eventually reaching an equilibrium state in which they are evenly spaced on our plane.
Deposit Layer
The deposit layer is where we bring in our image information, and is also represented by a layer of particles. To construct the layer we first take the image we wish to represent, and project it onto a 2D plane. We then create a fixed particle for every pixel, which lives at the center of the pixel, and has a charge Qk. The value for Qk will be based on the intensity value of the pixel; higher intensity values correspond to lower Qk values, and vice versa. Qk will also have a sign opposite to Qs.
Because the fixed particles in the deposit layer have an opposite signed charged to those in the particle layer, particles in the particle layer will be attracted to particles in the deposit layer. Areas of our density layer with lower intensity values, which are dark, will have a higher Qk value, which attracts more particles to it, and naturally forms denser patterns. In the opposite case, areas of the deposit layer with high intensity values will have smaller charge values, and won’t attract particles to this area, creating sparse point density, giving the impression of lighter shades.
Choosing Qs Values
By changing the charge value of our particles Qs, we can control the amount of attraction forces acting on them. Higher Qs values correspond to a more contrasted effect since the particles will be pulled closer to darker areas.
Performance
In the method described in the paper, we end up sampling every particle in both the sample layer and density layer in order to calculate the net force on a given particle. For N sample particles and M density particles we require (N + M) * N lookups per frame. This gets heavy pretty quickly, so the use of GPU based methods for larger particle counts is recommended.
Variations and Further Exploration
While this technique was developed with the intention of image processing, it can be abstracted as a semi-general simulation tool. The simulation itself works similar to a bunch of magnetic filaments on a surface; by changing the strength of magnets fixed under the surface, we can control the movement of filaments on top in interesting ways.
One way to exploit this would be to use something more abstract as our input image, like a noise-based texture, which can provide a generative feel.
Theres a really interesting take on Stippling by Paketa12 on Youtube which you can watch here. I decided to use his technique for creating a Voronoi cell centered at each particle. I found that layering the Voronoi cells with the Stippling particles provided a nice organic feel.
In this setup I use a positional lookup by finding where in the original image a particle lies, and retrieving the intensity of the image at this location. I use this intensity information to scale the particle’s size as well as influence the color. This adds some nice variation in the scene and helps contribute to that organic feeling.
Going Forward
Overall this technique provides some nice visual results as an accurate stippling effect and a general particle simulation. It plays nice with medium-sized 2D textures, so things like fluid simulations, reaction diffusion, etc, is fair game for experimentation.
The biggest drawback is definitely runtime performance, which will depend on the input texture size as well as the number of particles. I implemented this on compute shaders in OpenGL, which allowed for ~50fps performance with medium sized textures (<500 x 500) and ~5000 particles on a 2070 Nvidia Card. So definitely some optimization work to be had there.
References
Original Paper – https://www.researchgate.net/publication/344852879_25D_Computational_Image_Stippling
Paketa12 “Voronoi Stippling” Video – https://www.youtube.com/watch?v=NI_7rNwu8RA
Junichiro Horikawa Houdini Implemenation – https://www.youtube.com/watch?v=E6vuMfdYJnI