Filling Arbitrary Shapes with Non-Overlapping Procedural Floral Patterns

It seems that the aesthetics of our current time often favors minimalism. There also seems to be a time where everything (or at least, the nice ones) is filled with ornate decorative patterns: from furniture to fabric, from weapons to wares, from medieval manuscripts to Chinese ceramics... 

While there exist countless distinctive styles and associated motifs, perhaps a few features are commonly shared between such artworks of decorative nature: high spatial frequency (elements are evenly distributed avoiding large clumps or voids), planarity (major elements appear laid out on a 2D surface with minimal overlapping), and plasticity (patterns may be used to fill arbitrarily-shaped areas according to need).

These features, while more likely natural instinct rather than actual constraint for human artists, provide interesting challenges for procedural generation programs. Here I present a program that solves these challenges. While it focuses on floral and foliage-based patterns of somewhat specific styles, I believe the core ideas can be generalized to ornamental patterns of most kinds.

First, generate a relatively even distribution of random points, which will serve as "anchors" for ornamental elements (such as leaves and flowers), using Poisson disk sampling (Mitchel's best candidate algorithm). Compute the Voronoi diagram of these points, which tells us the boundary of each ornamental element, if overlap is not to occur.

The first major problem arises when considering the necessity of connecting leaves and flowers with vines or stems (as is in nature and the majority of depictions thereof). If the vines are to connect the Voronoi sites directly, then they will overlap with the leaves and flowers that reside in the cells. In other words, the vines must go around the Voronoi cells without cutting through them.

Alternative solutions are possible, to name one: use Delaunay triangulation instead of Voronoi, its dual, and place the leaves and flowers in the triangles whilst the vines walk along the triangle edges. 

However, I went with the idea of walking around the contour of the Voronoi cells, as the final result looks more natural. The subsequent problem with this approach is that the vertices on the contours of the Voronoi cells (henceforth referred to as "Voronoi corners") are spaced unevenly, for unlike the sites which can be deliberately placed, they're more of a complication produced by the former. This unevenness will likely produce kinks and unnatural tension on the vines (and perhaps other difficulties when attaching leaves and flowers to the vines). Therefore, yet another Voronoi diagram is computed with the (unique) Vornoi corners as sites -- a Voronoi of Voronoi. Then, a few iterations of Lloyd relaxation are applied to the new Voronoi to space out the former cell vertices more evenly. The former Voronoi diagram now becomes a Voronoi-resembling diagram where each cell is equilateral-polygon-resembling. 

Next, a spanning forest is created out of the Voronoi corners, with the edges selected from the (unique, undirected) edges of the cells of the former Voronoi diagram. The strategy I employed was based on depth-first search, yet at each node, I look at all available edges and pick one which will introduce the least abrupt turn. Optionally, bias toward one turn direction to create more whirly, winding, brain-coral-like patterns. When a path can no longer be continued, or not without introducing turns sharper than a certain threshold, I simply start a new path, preferably branching off from a previously visited node with unvisited neighbor(s), or otherwise completely anew from an unvisited node.

These rules can of course be set according to the look desired. One of the many maze-generating algorithms can perhaps also be employed. The parameters can be tweaked to favor smoother turns, longer runs, fewer trees etc.

Splines are subsequently used to interpolate the points on the vines, to produce a smooth and organic-looking result. Possible candidates include Catmull-Rom splines, natural cubic Bezier splines, and Hobby splines, etc. Catmull-Rom (C1 continuity) is perhaps the easiest to implement yet produces the least natural result. Both natural cubic splines, which guarantees C2 continuity, and Hobby splines, which sacrifices C- continuity for smaller variance in curvature, work well in this case. Hobby splines tend to have these larger "swings" to produce more circular paths, which can "eat" into the Voronoi cells too much sometimes. Natural cubic splines are more "true" to the original polyline, though they do look slightly less nice.

Another problem to solve before proceeding, is to clip the Voronoi cells by the desired overall bounding shape. For the simplest case, the bounding shape would be a rectangle of the dimension of the canvas; For general cases, it would be an arbitrary polygon with potential holes, as our program is set out to deal with from the beginning.

This can of course be achieved with a general purpose clipping algorithm. However, due to the nature of the polygons to be clipped (convex Voronoi cells that are much smaller than the bounding shape), the following approximative technique can be used for reasonably good results, and much less complexity and much smaller code size: For each cell to be clipped, compute all the intersections between the edges of the cell and that of the bounding shape. Put these intersections, as well as any vertex of the cell that's within the bounding shape, and vice versa, into a list. Compute the convex hull of the point list -- the hull can then be used as an approximation of the clipped cell. The additional benefit of this approximation is that the property of maintaining convexity can be advantageous in later steps.

The clipping step is performed before Lloyd's relaxation, and all boundary points are marked to be immobile during relaxation.

(In some of the illustrative figures, another approximative clipping algorithm is used, which "nudges" out of bound vertices inwards into bounds, keeping the original vertex count and correspondence intact for each cell. This convenient invariant was forgone for simplicity and robustness against complex bounding shapes introduced by the aforementioned hull-based algorithm, which was adopted in the end.)

Now that the scaffolding is done, it is time to plan out ornamental ornaments, more specifically: to assign each Voronoi cell to contain either a leaf or a flower, as well as a nearby vine segment to which the element shall attach. The optimal assignment would allow the element to rest at the most natural and least distorted orientation or pose.

For flowers, the following heuristic is applied: For each vine endpoint, lookup the associated cells (ones which have it as a vertex), and score them with two metrics: maximizing area and minimizing the turn angle between the tangent at the endpoint, and the line connecting the endpoint and the site. Intuitively, one wants large flowers that do not bend their necks backwards. The best cell is assigned to the endpoint, and may no longer be re-assigned.

For leaves, the following heuristic is applied: For each free cell, lookup all associated vine segments (ones which are among its edges), and find the cell vertex that is furthest away from each of these segments. The vine segment that can introduce the furthest of the furthest vertices prevails. Intuitively, most leaves in nature are somewhat oblong shapes and one wants to orient them along the primary component of the cell shape. Each leaf is roughly bounded by the triangle formed by the segment and the far vertex.

Until now, thanks to the even Poisson disk sampling, all the cells and thus their contained elements are roughly the same size, which, for certain designs, may very well work. However, in many other designs, flowers are typically the more prominent feature compared to leaves, occupying larger area and containing more detail. To enable such designs, the following modifications are made to the process:

During the initial sampling with Mitchel's best candidate, each point can be given a higher "weight", which makes it "appear" closer to prospective points, causing the latter to favor locations further from it. These "heavier" samples then correspond to larger cells in the Voronoi step that follows. Power diagrams, a generalization of Voronoi diagrams, are perhaps another viable, yet more complicated approach to this effect.

During Lloyd's relaxation step on the corners, further measures need to be taken to prevent the contrast in sizes from being undone by the averaging tendencies of the operation. Instead of directly moving a corner to the centroid of the Voronoi cell of which it's site, everything is now calculated in forces, as if in a physics simulation. The corner gets a small "push" toward the centroid, as well as a "repulsion" from heavy initial sites. Small steps and simple Euler integration proved reliable.

Finally, during spanning forest creation, when starting a new path, a corner of a heavy site will be picked if eligible; when a path reaches an eligible corner of a heavy site, it ends there. To be considered eligible, the site must not introduce sharp turns, as before. In other words, this essentially ensures that the heavy sites will end up being flowers. The cells which would've been assigned to be flowers by the original heuristic but are not blessed by heavy sites, are now given the role of "little flowers", or "buds", depending on the design.

Any un-assignable cells (typically few) at the end of the process are assigned "fallen petal". Thus each cell is one of the four: leaf, flower, bud, petal. Again, depending on different designs, these can correspond to other elements featured by the plant depicted. 

Now that the type, orientation and bounding shape of each of the ornamental element are fixed, the actual rendering of the element is up to the procedural generation artist. Here only a few techniques are listed for reference:

To maximize space utilization when placing petals of a flower, cast great many rays pointing in all directions from the center of the flower, intersecting them with the cell boundary. Pick rays that travelled long enough before intersection to grow petals along. Bezier curves can be used to model the shapes of leaves and petals. Randomize the order of the petals if they overlap, to produce a more organic look.

In addition to generating ornamental patterns of various shapes and sizes, the program can also be used to generate typefaces, turning any input font to one lavishly decorated by flowers. A few open fonts underwent the conversion, samples below. The colors are implemented with COLR table of the OTF format.

As a stress test, the algorithm is also applied to every frame of the popular 1-bit video, "Bad Apple".

The program is written in Dither, a new programming language for creative coding, made by the author.

The source code can be found here (presets demo), here (font demo) and here (video demo).