samedi 20 juin 2009

Kusama's patterns II

This is a follow up of this post. I implemented the algorithm I had in mind and here is the raw output:

Before I explain how it is made, try to find some regularity in the pattern... I think it is possible to see some.

Let me first say that I'm not satisfied at all with this algorithm. It is extremely slow (that's why the image above was rendered without antialiasing at 350x350 pixels). I cannot imagine rendering it at high resolution, let alone use it in pattern piling algorithms. And even at a more fundamental level, the dots are not nearly as densely packed as in Kusama's pattern.

The algorithm works in the following way. First decompose the plane into a regular tiling by squares. The idea is that for each pixel, we will draw random dots into the square it belongs, and color the pixel differently if it belongs to one of the dots. Problems may occur near the boundaries of the squares. We do not want to force the dots to belong to a single square (it would give some obvious and unwanted feature to the resulting pattern), but instead allow them to overlap between the squares. The randomly chosen dots crossing the boundary between our square and a neighbour should be the same as the random dots chosen when computing the color of a pixel in the neighboring square. If not, the pattern cannot be continuous across the boundary.

One way to achieve this could be to compute for each pixel all the dots with center lies in the squre it belongs or in one of the eight neighboring squares. But this is not very efficient. There are many circles in the neighboring squares which do not touch the central square.

So instead, I proceeded as follows. First, we do not like the pixels which lies near the corners of the square, because they can potentially belong to dots overlaping with the three other squares around the corner. Let us eliminate them right away by drawing a dot with a random center and radius, but such that it contains the corner. To choose the "random" center and radius, we use a pseudo-random generator which takes the coordinates of the corner as seed. In this way, the same dot will be drawn at the corner when performing the computations for any pixel belonging to the neighbouring squares, and the pattern will be continuous. Here is the pattern we get:

In contrast, here is what you get if you do not choose the seed of the pseudorandom generator to be at the corner. In each square, we chosed the radius and center of the dot idependently and we do not get a continuous pattern.

We put dots at the corners. To reproduce Kusama's pattern, we will of course require that the extra dots we will add do not intersect the dots already drawn, so none of the extra dot can come close to a corner. Still they can come close to the edges, so in the same spirit, we put dots along the edges, making sure that the dots drawn by two neighbouring squares along their common boundary coincide. We get this kind of patterns:

Finally, we will the remaining space in each squares with random dots. Now, to see if a pixel belong to such a dot, we do not need to know what's happening in the other squares.

To achieve the continuity of the pattern, it turns out to be necessary to choose the dots at the corners to be slightly larger than the mean size of the dots drawn inside the square, and I think it is possible to see it in the first image above. I doubt someone would notice it by themselves, though.

I thought this would allow to reproduce Kusama's pattern, but it's not really the case. It turns out to be impossible to pack dots as densely as she does just by choosing randomly the centers and radius of the dots. One slight improvement is to start to draw the large dots first, and then try to fit smaller dots. The first image below uses this technique, whereas the dots were choosen completely randomly in the second one.


Still, it is not as close as I would like to Kusama's pattern. So we have an interesting question... how to reproduce the densely packed dot pattern of Kusama with an algorithm? Randow dot throwing doesn't work. As was mentionned in the previous post, we could realize it as a Truchet pattern, writing down explicitly in the algorithm the center and radius of the dots on each tile, but this is not very elegant.

If anyone has an idea, please comment...

Aucun commentaire:

Enregistrer un commentaire

Remarque : Seul un membre de ce blog est autorisé à enregistrer un commentaire.