Follow by Email

Tuesday, January 31, 2012

Texture, Part 1

I am a bit of an expert on seamless tiling textures, since I created nearly all of the paper textures that ever shipped with Painter, Dabbler, Sketcher, and Detailer. But, how they were created?

This is the first post of many that actually resurrects the application, called Texture, which was used to create all the paper textures in Painter. This application hasn't run since 1996, and was forgotten until now. It was a secret application, that never saw the light of day outside the walls of Fractal Design and my house. But history is littered with lost arts. So now I will show you the art of making stuff that helps you to make art.

Speckles

It mixed tiling patterns with Fourier transforms with speckles. A speckle (or speckle pattern) is a set of points in the plane that repeats. But one where you almost can't see the tiles.

I show you one to the right, which has about 1.4 repeats of the tile in it. It does take some time to see the repeat, but it is there.

As opposed to the harsh repeat pattern of rectangular tiles, a speckle is visually pleasing and it is intended to be totally seamless.

It also seems like a very good start for creating paper textures because the texture has only one predominant spatial frequency. Now, a typical paper texture in Painter is 256x256 pixels, although they are scalable. This speckle has 1000 points in the tile, meaning that any derived paper texture will have about (256 x 256) / 1000 or about 65 pixels per item in the texture.

Creating a Speckle

First, the a tile is seeded with a number of random points. Lets say that you have constructed a function urand(), that returns a random floating point number on the range 0...1. Then the following code will suffice to create a random 1000-point speckle:

#define MAXSPECKLE 10000
int i, npoints = 1000;
point speckle[MAXSPECKLE];
for (i = 0; i < npoints; i++)
{
    speckle[i].x = urand();
    speckle[i].y = urand();
}

The random speckle is shown to the right. The dots are smaller because the average minimum distance is quite small, and we need to be able to see the individual dots.

Then we do an interesting trick. We iterate an anti-gravity transform to push the points apart in the plane. This uses a technique of mutual-avoidance to make them regularly spaced.

After about 10-12 iterations of the mutual-avoidance transform, this set of speckles looks like the one shown to the right. The spots are larger again because the average minimum distance has reached a steady state of about 6 to 8 pixels.

Tiling Math

On a wrap-around tile, certain things we take for granted like distance formulas become a bit different. For any two points p1 and p2, the distance can't be calculated in the normal way. We must account for the wrap-around.

To do that, we have to make a wrap-around rule that says if a point is more than one-half a tile forwards, then the image of that point behind us is really the one we want.

So, something like point-to-point distance becomes a bit more complicated:

float dist(point p1, point p2)
{
    float dx, dy;
    dx = p1.x - p2.x;
    if (dx > 0.5) dx -= 1.0; else if (dx < -0.5) dx += 1.0;
    dy = p1.y - p2.y;
    if (dy > 0.5) dy -= 1.0; else if (dy < -0.5) dy += 1.0;
    return sqrt(dx*dx + dy*dy);
}

The above function implements the wrap-around rule for a tile that repeats in both x and y.

To implement the mutual-avoidance iteration, we first make a pass over all the points in the speckle, looking for neighbors within a small distance. This optimum distance is usually computed in the following way:

effectRadius = 2.5 * sqrt(2 / (points * sqrt(3)));

This assumes that the tightest packing of points is a triangular packing. The 2.5 is thrown in as a fudge factor to make sure we get enough neighbors to do the right thing. Then we compute a motion vector for the point that is designed to push it away from its nearest neighbors. The following code shows this motion vector gathering pass. Note that, to right I have placed the initial state and the first six iterations of mutual avoidance, so you can see the effects of the iteration.



int i, j;

float d, mindist, avgmindist;
point *p1, *p2;
vector vs;
avgmindist = 0;
for (i = 0; i < npoints; i++)
{
    p1 = &speckle[i];
    vs = vector(0,0);
    mindist = 1;

    for (j = 0; j < npoints; j++)

    {
        if (j == i)
            continue;
        p2 = &speckle[j];
        d = dist(p1, p2);
        if (d > effectRadius)
            continue;
        if (d < mindist)
            min_d = d;
        vs += (*p1 - *p2) / (d*d);
    }

    p1->v = vs;

    p1->dv = length(vs);
    p1->mindist = mindist;
    avgmindist += mindist;
}
avgmindist /= npoints;

The above code also computes an average minimum distance, so we can properly scale the motion vectors for the points.

Next, we compute the sum over all motion vectors' velocities (lengths) and create a factor that helps us normalize the motion vectors.

float dvs, factor;

dvs = 0;

for (i = 0; i < npoints; i++)
{
    p1 = &speckle[i];
    dvs += p1->dv;
}
dvs /= npoints;
if (dvs == 0)
    factor = 1;
else
    factor = (effectRadius * 0.04) / dvs;

This factor can be used to scale the motion vectors to complete the avoidance iteration. The points are now moved. They must be placed back on the tile if they wander off, of course.

for (i = 0; i < npoints; i++)
{
    p1 = &speckle[i];
    p1 += factor * p1->v; // move the point

    if (p1->x < 0.0)
        p1->x += 1.0;
    else if (p1->x >= 1.0)
        p1->x -= 1.0;
    if (p1->y < 0.0)
        p1->y += 1.0;
    else if (p1->y >= 1.0)
        p1->y -= 1.0;
}

And that's how mutual avoidance works, in a nutshell.

The best thing about speckles is that they can also be used for so many other things. One of these is visually interesting, since it mimics the arrangement of cells in the back of your eye. For instance, to the right we can see a section of the human fovea, the dense cluster of photoreceptor cells in the back of your eye. It is interesting how often cells land in a hexagonal tight-packing.

One day, when implementing Texture, I came across a computation geometry trick called Voronoi maps. These are like a cellular partitioning of space around a set of points. Arranged so each point gets its own well-defined little capsule of space. This technique was very interesting visually.

Here you see a Voronoi map applied to a speckle. The speckle was created by starting with 100 random points and iterating the mutual avoidance iteration a mere 9 times.

Then a Voronoi map was created on the tiling plane. This is a bit trickier than constructing a Voronoi map in general, but really only the distance function needs to change.

I won't go into how I create them, but I will give a link to a remarkably efficient technique for creating them. Most techniques for creating these maps depend upon the simple in-circle test.

But there are other ways to treat points: connecting them. An example of this is called a tree of points.

Spanning Trees

A spanning tree is a single graph that connects all the points of the graph, but which does not contain a single loop. To construct one, maintain a tree number for each point. When you connect two points, set their tree numbers to the minimum of the two tree numbers of the two points. Do not connect them if they have the same tree number, since that would imply a loop.

So, the art in spanning trees can be put simply: in what order do we connect the points?

I call this the function type of the spanning tree.

This kind of function is used in constructing halftone dot patterns as well, but that's a post for another day!

Here we have one spanning tree, constructed so that the bonds are favored to fan out from the center.

This kind of tree is useful in producing growth-like looks. Really, it is more like the growth of bacteria or lichens, since it is constrained to lie in the plane.

Another kind of spanning tree is constructed on the same points, but in this case, it is designed so the bonds are favored in a direction perpendicular to those of the first spanning tree. This is useful in creating rose-petal patterns and even fingerprint patterns.

There are more things you can do with speckles, and bridging the gap between geometry and image processing is the key.

We will talk more about that in future Texture posts.

But, have no fear, I have taken step 1 in bringing the art of creating paper textures back from the dead!





5 comments:

  1. Replies
    1. All my own. Written in Objective C on Macs. Hell, I've shared a lot of the code with you here. ;-)

      Delete
  2. Dear Mr. Zimmer:
    I wrote to you some time ago, perhaps 2 years, asking permission to use one of the patterns you developed, for a project of my own, a Photoshop extension for artists. I call it Printmaker. I finished this project, which incorporates your pattern and others as well. Here's a very brief demo of Printmaker. https://youtu.be/EdUc_JcwaUo
    I'm a professional artist, not a software person, so I feel out of my depth in addressing you. However, my Ps extension has proved very useful to me, and I hope other artists may take an interest. Many thanks for your contribution to the project.
    My website is www.elliottbanfield.com

    ReplyDelete
    Replies
    1. Really nice work, Elliott! It's nice to see other creators out there that are so interested in patterns.

      Delete
    2. If I may go on a bit further, just to be clear: you developed seamless patterns for the purpose of simulating the texture of canvas and paper. (As described above) My interest is, I think, a bit different.
      I see patterns in nature: in foliage, rocks, fabrics, the bark of trees, animal's fur, etc. Obviously, I'm not the only one. For example, in the nineteenth century, wood engravers used contrasting patterns to make detailed pictorial illustrations. My Ps extension is intended to follow in the tradition of those old engravers. With it, I can, so to speak, paint with patterns. (Not that I'm Picasso, of course)
      Best wishes, EB




      Delete