Stippling and Blue Noise – Jose’s Sketchbook
It’s been some time for the reason that final submit, and the reality is I’ve spent most of my spare time currently dedicated to my photography. Again nonetheless to extra technical issues, one of many matters I discover fascinating is NPR methods, and notably Stippling as an attention-grabbing instance of them. I’ve been studying about it for a while now and learnt a few attention-grabbing issues alongside the best way, so I believed I might share them in a submit.
When stippling a picture, we’re principally desirous about producing a distribution of factors with a density distribution matching the tones of the unique picture, the dimensions of the factors is usually fixed, and we add kind of of them to create darker or lighter tones. In these areas it is very important generate a distribution freed from sampling artefacts, which manifest as patterns within the picture — the attention is de facto good at selecting up these.
So primarily all we want is a giant variety of factors distributed randomly, and a approach of quantizing their required density after we place them over the picture. To generate the factors, the primary method could be utilizing purely random factors. It seems, nonetheless, that pure randomness doesn’t result in aesthetically pleasing outcomes, as factors are inclined to litter in areas and go away empty areas. On the opposite excessive, utilizing a superbly homogeneous scheme — say a grid- would result in artefacts within the type of aliasing. We thus want one thing nonetheless random however nonetheless considerably a bit extra even.
Random sample on the left, Blue noise on the best. Picture from |Kopf 06|
Within the in-between land, there’s a flavour of noise known as Blue Noise, which is the title given to a selected distribution of frequencies with minimal low-frequency parts and no concentrated spikes in power. Which means we have now no structural aliasing given by the low frequencies, and even spacing with minimal cluttering. It’s typically accepted that blue noise properties make for a few of the greatest sampling patterns for a variety of purposes (see [Lopez 10]).
Noise patterns: the highest picture exhibits structural repetition. The center one shows radial patterns and clustering. The third one shows blue noise traits. Pictures from |Kopf 06|
A method of producing level distributions with blue noise properties is via a Poisson-Disk Distribution [Cook 86]. One of the simple methods of producing such distribution is through the use of a so-called Dart-Throwing Algorithm [Cook 86], which generates candidate factors in a random vogue over the airplane, however will solely settle for every candidate if it lies at a minimal distance from each beforehand accepted pattern. McCool and Fiume [McCool 82] describe a extra sensible variant
of dart throwing, the place the dart radius steadily decreases as extra samples are positioned. The Dart-Throwing algorithm is due to this fact inherently sequential and sluggish as a consequence of its quadratic complexity, however the high quality of the outcomes is nonetheless excessive.
An necessary property of any distributions generated with the aforementioned variation proposed by McCool and Fiume is its progressiveness: Equally to some low-discrepancy sequences, if we put all of the generated factors into an inventory of N parts, and draw solely a portion of that record [1, N < M], the ensuing level distribution additionally covers the whole airplane (versus sweeping it), however merely does it with a decrease density. That is necessary as a result of it signifies that if we are able to stipple a spatial area with a given density by plotting all of the factors of a tile T, we may even be capable of generate any lighter density through the use of the identical T by plotting a smaller set of its factors.
The quantity of factors we usually have to stipple a picture, which is within the vary of 1000’s in the most effective of circumstances, makes the easy implementation of the dart-throwing algorithm impracticable. An enormous a part of the issue we’re dealing with with stippling is how you can effectively generate heaps of factors in a blue noise distribution. There’s a important quantity of analysis on the matter, and the remainder of the submit will take care of a few approaches I favored and applied myself, together with notes on associated work.
To generate PD level distributions with blue noise properties there are a number of households of approaches, amongst which we have now:
- Incremental strategies, which place samples sequentially. The Dart-Throwing algorithm described above is a primary instance of them, however one might simply give you extra refined implementations which made use of auxiliary buildings similar to hashing grids or bushes to scale back the price of the nearest-neighbour lookups. A proposal I discovered notably attention-grabbing is described within the paper [Lopez 10], additional particulars on the implementation of this methodology are offered under.
- Excessive-throughput strategies: these normally depend on a heavy precomputation stage however a really quick execution time. A major instance of this sort of algorithm is [Kopf 06], additionally applied and described on this submit. Additionally, spectacular outcomes are obtained by [Wei 08] with a GPU-based Poisson-Disk distribution technology algorithm, orders of magnitude sooner than the sequential method.
- Approaches based mostly on Constrained Voronoi Diagrams (CVD), the place every pattern corresponds to a cell. These approaches, regardless of being extraordinarily costly in time, generate most likely essentially the most pleasing distributions. [Hongwei 09] report good points of 10x in execution time of their paper.
Constrained Voronoi Tessellation to generate samples. Picture from the paper |Hongwei 09|
The variations between kinds of approaches are high quality (depicted as even, perceptually pleasing distributions) and execution time. The perfect outcomes appear to be obtained with CVDs or sequential algorithms, however their execution instances are orders of magnitude slower than high-throughput approaches such because the one based mostly in Wang Tiles, which run in actual time. These later generate a extra noisy consequence nonetheless, which as we’ll see, will not be a lot aesthetically pleasing for the actual case of stippling – However blue noise sampling could also be used for quite a lot of purposes similar to object- or texture-placement because the authors present within the [Cohen 03], the place the density of the distribution will possible be a lot much less dense and pace is essential.
The primary one of many approaches I attempted is the one described within the paper [Lopez 10], which is a extra environment friendly extension of a sequential algorithm with good high quality outcomes and respectable execution time.
The important thing concept behind the method is straightforward: having a pattern level on the airplane, and a minimal acceptance distance limiting how shut another pattern can get to it, we construct a disk and generate all subsequent samples on its boundary*, as a substitute of randomly on the airplane. For every accepted new pattern, we calculate the intersection between its disk and the at the moment energetic one and subtract a portion of the energetic boundary space — so no new samples will overlap. When there’s no remaining boundary on the energetic disk, we de-queue it and proceed with the subsequent one.
This defines a sample in how the samples are generated, as new samples are solely generated on the at the moment energetic disk, and their corresponding disks are queued for later processing. The samples then develop throughout the picture from an preliminary seed (which it’s fairly pretty to watch!). A secondary picture buffer is saved to hurry up disk overlapping checks, the place disks are rasterized. As a way to settle for a pattern we have now to first examine whether or not the corresponding rasterized disk would overlap a non-empty pixel within the disk buffer.
The acceptance distance for any pattern is given by the density distribution, i.e. the quantity of black, within the area coated by the pattern on the supply picture
* Extra exactly, an angle is sampled on the remaining boundary of the energetic disk. The brand new disk might be positioned on the road that elements from the centre alongside the course outlined by this angle, at a distance given by the picture densities of each the energetic and the brand new disk.
Stippled picture generated with the AIS algorithm. Click on for full decision picture.
Implementation notes
As a part of the check utility offered on the finish of this submit, I labored on an implementation of the AIS algorithm utilizing C#. Regardless of the operating instances I’m attaining usually are not practically as quick as those reported within the paper, they’re not too unhealthy for the standard. Though that is conveniently omitted within the paper, care needs to be taken when implementing the disk adjustment heuristic to take care of sub-pixel disks, particularly as they have an inclination to make the method diverge, and should even get the algorithm caught because of the lack of ability of the disk picture buffer to deal with disks smaller than 1 pixel. I discovered utilizing an accurate disk space calculation (versus a squared window approximation) to provide fewer artefacts albeit barely slower. Darkish photographs such because the zebra displayed within the screenshot under are remarkably tough to deal with robustly because of the excessive distinction and pattern densities required
This being mentioned, the outcomes look fairly good most often. There’s a free parameter which controls the general density of the stippled picture — not each picture is fitted to a set worth of this parameter, and tinkering with it helps obtain optimum outcomes.
The second method I attempted belongs to the high-throughput household described above. This algorithm depends on a heavy precomputation stage to generate an auxiliary construction known as Wang Tiles utilized in mixture with PD distributions to realize quick operating instances.
Wang Tiles [Cohen 03] are a development which allows arranging a finite set of parts (the tiles) in a non-periodic (pseudorandom) sequence to cowl the airplane. The tiles are squares which have a color assigned to every certainly one of its 4 edges. The algorithm states {that a} tile can solely be positioned if the color of its edges matches these of the encompassing tiles which have been beforehand positioned. For any set of tiles whose parts fulfil the required restrictions, a component is chosen randomly.
Set of Wang Tiles organized in a legitimate configuration. Picture from |Cohen 03|
We begin with a tile and sequentially insert random tiles from left to proper, merely guaranteeing that the left edge color on every newly positioned tile matches the best edge color of the final one. As soon as we’ve reached the best certain of the world to cowl, we proceed constructing a brand new row, now matching the left and high edges with the tiles from the earlier row. That is known as the scanline algorithm.
We begin with a set set of tiles and place them satisfying 1 or 2 restrictions relying on what number of neighbour edges we have to match at any given time. For C potential edge colors, we’ll want no less than N*C2, N>=1 tiles out there to fulfill each restriction on the highest and left edges. N determines the variety of out there decisions for any placement, from the place we selected utilizing a uniformly distributed random quantity.
What it’s attention-grabbing in regards to the sequence generated by the aforementioned algorithm is its aperiodicity, its lack of construction or repetitive patterns.
The aperiodic sequence is generated from a finite set of tiles. Picture from |Cohen 03|
Now, what will we put within the tiles? Wang Tiles have been used to synthesize textures from samples; we’ll use them to cowl the airplane with a noise sample, generated from a finite, comparatively small, set of PD distributions. This course of is described within the paper [Kopf 06]. Having this, all we have to do at runtime is execute the scanline algorithm to cowl the specified picture space with tiles from the pre-computed set.
Texture synthesis from samples. Picture from |Cohen 03|
Noise synthesis from samples. Picture from |Cohen 03|
Earlier than that, there are a pair extra particulars to fret about: edge seams and recursiveness.
Edge Seams
By merely selecting random squared samples of textures or noise patterns after which placing these collectively subsequent to every, we received’t assure that the seams match. We have to construct the tiles in such a approach that, every time the sting colors on the other edges match, so does the picture on the tile.
To do that, the authors suggest selecting sq. samples for the colors themselves, after which combining these pattern colors to construct every tile (4 supply photographs for every tile) as depicted within the determine under:
Tile merging: a supply distribution is generated for every tile, after which merged with 4 extra distributions corresponding to every edge color. This can make sure the contents of adjoining tiles match the boundaries. Picture from |Kopf 06|
This manner, since every matching edge comes from the identical picture, they may align correctly.
For the case of blue noise samples nonetheless, issues get a bit extra concerned: we not solely want the noise patterns to match on the sides, however we additionally want the ensuing merged tiles to protect their PD properties: we don’t need merged samples to type clusters. The authors of [Kopf 06] suggest making use of a Voronoi diagram containing all of the samples to be merged after which constructing a seam from the trail that minimizes a price operate which penalizes close by samples. Put in plain phrases, this implies merging the supply PD distributions by reducing alongside an irregular seam passing by these areas the place factors are additional away on common.
Minimal value seam generated from traversing the Voronoi boundaries. The sting value is proven in crimson.
After this stage, we’ll have a set of tiles that we are able to blindly prepare in accordance with the scanline algorithm to generate a sequence which may even protect PD distribution properties. Word that producing the Wang Tiles is the majority of the work on this algorithm, but it surely’s a one-off course of. After that, we’ll be capable of cowl as a lot space as we wish with blue noise with out having to run a sequential dart-throwing algorithm at runtime.
Recursiveness
The second problem we have now to fret about is: we all know our supply tiles are progressive, and due to this fact plotting a subset of them produces a much less dense, however equally filling noise distribution. We use this property to generate mild shades on our stippled picture – but when we occur to require extra density than the utmost our tiles’ distribution can present, we received’t have sufficient factors!
We thus have to make the tiles recursive: permitting any tile to be subdivided right into a set of NxN smaller tiles (constructed following the identical edge-matching guidelines) which provides as much as N2 extra factors than the supply tile.
Tile subdivision. Picture from |Kopf 06|
Recursiveness together with Progressiveness are the properties that can permit us to realize arbitrarily darkish or mild shades within the stippled picture.
Placing all of it collectively
The stippling algorithm based mostly on Recursive Wang Tiles is predicated on the next steps:
Preprocessing:
- Let C be the variety of edge colours, generate a whole set of N*C2 supply PD level distributions.
- Generate C extra PD distributions, one for every edge
- Construct the entire set of distinctive N*C2 Wang Tiles by merging every supply distribution with the 4 edge distributions. Word that the unique supply distribution received’t match on the seams, however these merged ones will.
At runtime: Cowl the supply picture with a non-periodic sequence of the pre-generated tiles; for every tile, resolve whether or not to insert every level based mostly on the required picture density. If we’ve inserted all of the factors on a tile distribution and we nonetheless require extra density, subdivide the tile.
Stippled picture generated utilizing the Recursive Wang Tiles methodology. Click on for full measurement.
Word that the picture generated with this methodology is considerably noisier than the consequence achieved with AIS, nonetheless, when you run the offered software program you’ll discover how a lot sooner this methodology is (excluding the preprocessing, that’s).
To complete the submit, I needed to offer a touch of what I think about a failed check both as a word to self or in case anyone studying that is prepared to give you an concept to make it work sooner or later ????
AIS prolonged to color. Pointillism?
Regardless of personally discovering the monochrome stippled photographs to be lovely, one trivial extension I considered was extending the AIS algorithm to plot colored disks by averaging the underlying picture pixels. I used to be aiming for a considerably pointillist impact. Nevertheless, the picture doesn’t utterly make it for me as a result of the method is basing the stipples (the strokes on this color model) solely on the darkness of the picture, utterly ignoring the homogeneity of the tone — this may forestall darkish broad strokes from showing on the consequence it doesn’t matter what. Clearly, that’s what the stippling algorithm is designed to do: generate darkish shades from dense clustering of factors, however I do suppose one thing like this may very well be achieved:
An utility implementing the Adaptive Incremental Sampling and Recursive Wang Tiles algorithms described on this submit are offered. The supply code is written in C# underneath Visible Studio 2010. In the event you simply wish to run it, there are binaries already constructed, together with a pre-generated set of Wang Tiles to make use of included within the compressed file.
Precompiled binaries: stippling.zip
Supply code repository on GitHub: https://github.com/joesfer/Stippling
Stippling utility: AIS and Wang Tiles approaches out there
Stippling utility: Wang Tiles generator, with (optionally) detailed step breakdown.
[Cook 86] Cook dinner, R. L. 1986. Stochastic sampling in pc graphics. ACM Transactions on Graphics 5, 1, 51–72.
[McCool 82] McCool, M., and Fiume, E. 1992. Hierarchical Poisson disk sampling distributions. In Proc. Graphics interface ’92, 94-105.
[Kopf 06] Johannes Kopf and Daniel Cohen-Or and Oliver Deussen and Dani Lischinski. Recursive Wang Tiles for Actual-Time Blue Noise. ACM Transactions on Graphics (Proceedings of SIGGRAPH 2006).
[Hongwei 09] Hongwei Li, Diego Nehab, Li-Yi Wei, Pedro Sander, and Chi-Wing Fu. Quick Capability Constrained Voronoi Tessellation.
[Cohen 03] Michael F Cohen, Jonathan Shade, Stefan Hiller, Oliver Deussen. Wang Tiles for Picture and Texture Technology. ACM Transactions on Graphics 22 (3) p. 287.
[Lopez 10] Ignacio Ascencio-Lopez and Oscar Meruvia-Pastor and Hugo Hidalgo-Silva. Adaptive Incremental Stippling utilizing the Poisson-Disk Distribution. Journal of graphics, GPU, and sport instruments.
[Wei 08] Li-Yi Wei. Parallel Poisson Disk Sampling, in SIGGRAPH 2008, Affiliation for Computing Equipment, Inc., March 2008