Patterns, Part 4

There are some patterns that just can't fit together without some kind of grammar: patterns in how the pieces interrelate. Like grammar in language, this usually means a set of rules. And this is the way most patterns work in the real world: patterns in the interaction of people, patterns in code, patterns in mathematical rules and groups, patterns in messages. We will examine a simple grammar: the even-odd grammar, and also a much more complex grammar, with a larger set of rules.

The even-odd grammar is an easy one: imagine a checkerboard. There is one rule for the black squares, and a second rule for the white squares. Let's look at a few examples.

even

odd

The first pattern, shown above, is not obviously an even-odd pattern. But its rule set says that in even squares, we must choose from the left basis set. These have a common trait. The yellow is in the upper left and the orange is in the lower right. The priority of the elements is the other aspect, and that's what makes for two elements in the even basis. In the odd basis (right) the common trait is that orange is in the upper right and yellow is in the lower left. And they have their own priority. This set was actually an image hose in Painter originally. But here I have dissected it further and given it a grammar.

Now, we mentioned a checkerboard, which is also a pattern. This has an even rule consisting only of a black square and an odd rule consisting of only a white square. But all checkerboard-like patterns can be represented this way, for example this one.

Yes, this looks like the pattern used on non-slip metallic surfaces. You see it in industry and it is quite familiar. Like the plainweave pattern, it has a horizontal and a vertical symmetry about it, like the weft and the warp of a weaving.

The basis set for this is quite simple and ingenious.

even

odd

The even basis set consists of one image: the horizontal line. Because the lines intrude into the other square, you can see the ends of the vertical line in the horizontal piece. The odd basis set is similar, but rotated 90 degrees.

This illustrates the simplest form of even-odd pattern grammar, like the checkerboard but a little more interesting.

Now we are going to go a bit loopy. We can modify a simple plainweave grammar to include loops and such. You can see that the crossings behave in a completely entangled even-odd way, and this is enforced by the grammar we used to construct it.

My pattern program can generate these in a random fashion, but I can also draw them, using the grammar to enforce the placement of elements from my brush.

In this case, I carefully drew this one to avoid small loops and to include some knots. I was going for a particular aesthetic.

I just love loops and knots. There is a kind of secret language to them. And I guess this is what I am revealing here!

even

odd

The basis set for this contains the plainweave basis set as a subset. Then I have included some elements from my curved grammar. The common aspect to each element is that the lines meet at the center of the square edges and they all have a direction that, at the edge, becomes horizontal or vertical (orthogonal).

Just to show that we can create branching and tree-like patterns with an even-odd grammar, I have included this example. Unfortunately there are some cycles in it as well. But, all in all, a complex branching pattern exists that can branch in any direction.

Like the loopy pattern, this one has an aspect of visual complexity to it.

First, it's totally not obvious (to me) that it can be constructed from a pattern basis set. I discovered this one while playing with rendered pattern elements in my patterns application. This particular rendering is totally random.

even

odd

The basis elements are appallingly simple. They are T's. The even set has horizontal crossing and either an upwards or a downwards branch. The odd set is a 90-degree rotation of the even set, with a vertical crossing and either a leftwards or a rightwards branch. It's actually kind of clean the way it's constructed!

This pattern was one of the image hoses included with Painter 3 when it shipped. But with Use Brush Grid gone from the nozzles palette, this can't be done any more. Sad, actually.

I will leave it to you to figure out how it can be constructed as an even-odd grammar. There are two basis squares per rule, and two rules, one for even and one for odd.

This one is called the knobby pattern, by the way. It does contain some dots, and also some circular holes.

You might have noticed that there is a 45-degree tilt to many patterns that you can make with the even-odd rule. And a checkerboard becomes a regular lattice in some ways when you turn it 45 degrees.

Now let's turn to a more complex grammar. I had an idea that a lattice with square holes cut out of it in 3D could be a pattern.

Here is an example of the principle in action. You can see the square lattice and the holes cut out. Once they are cut out, the sides need to have dimension lines, giving them faux depth.

Once I drew this, I realized that there were several cases and the grammar would be complicated. In all, I counted eight possible shaded square cases, including the entirely inside and entirely outside squares. So let's look at how the elements are encoded as they are placed on a regular grid.

We can see that, to get the shaded look, we will have to tag a number to each case and allow them to be placed in a geometrically reasonable configuration.

So the real question becomes: what elements exist and what is the possible set of connections between the elements?

This means we will have to enumerate all the possible elements (8 elements as it turned out) and also enumerate all the ways the elements fit together. Of course, this turned out to be a time-consuming process. And, when it was implemented in patterns, it had a few bugs. But I am good at finding and fixing bugs in logic, fortunately!

Here you see the eight elements in schematic form and the connection diagrams that form the grammar that controls the placement and configuration of the elements.

Element 0 is the entirely inside square, and element 7 is the entirely outside square. I have used the same convention as the earlier diagram.

The left table shows what configurations are legal vertically, and the right table shows what configurations are legal horizontally.

There probably should be more obvious symmetry to the table, which might be had by reordering the numbering of the elements. But this grammar does work.

You can see a rendering from the patterns application, generated entirely by random placement and adhering to the grammar as advertised.

It definitely can achieve the proper appearance, which looks like an orthogonal shaded view of blocks with shading. Perhaps like a shaded bitmap.

So pattern grammars can be molded to solve real problems in configuration and generate looks that are interesting to our eyes.

But I have only scratched the surface, really.

Hard Problems

I like to solve hard problems, which is good since that's my job. This involves significant analysis, and complex problem-solving time and time again.

I have been sharing some of the details of the complex problem solving required to produce features in Painter, but for once I will discuss a tiny, almost lost bit of work I did at my current job. This involves a problem I have been seeking to solve for at least ten years: the lofting problem.

You might be asking yourself how I can talk about it, since it involves my current work. The answer is that this work is now in the public domain, since the process I am about to describe is detailed quite explicitly in US Patents 7,227,551 and 7,460,129. It is also not particularly secret or unavailable since it can be had by using Core Image, part of Mac OS X, as I will indicate.

The Lofting Problem

A Text Mask to be Shaded

If you have a bit of masked information, like text, it is classic design to create a version of the text that is 3D. I'm not talking about extruded letters, which are kind of passé. I'm talking about surface texture that makes the letters look puffy. And stand out. Here you see some masked text. Optima extra bold.

While working on something quite different, another employee, Kok Chen, and I came across something truly amazing.

We solved the lofting problem.

The Wrong Answer

Now, to introduce you to this hard problem, let me show you what happens when you try to create puffy text in Painter.

Here is the result. To do this, I used Apply Surface Texture using Image Luminance, and cranked up the Softness slider.

But all this can do is soften the edge. It can't make the softness sharper near the edge, which is required to get a really classy rendering.

The Right Answer!

Using the lofting problem solution we thought of, you get a much better rendering. The corners have a shine that goes right into them, because the curvature of the surface is continuously approaching a sharp point at the corner. Yet remains pleasingly rounded in the center.

Think of a piece of rubber or flexible cloth tacked down to a hard surface at all points along its edge, and then puffed full of air from underneath: lofted.

I think you get the point. The difference is like night and day! Before I implemented this in Core Image, this was not an easy effect to achieve, and probably couldn't even be done without huge amounts of airbrushing.

In Core Image, you might use the Color Invert, Mask To Alpha, Height Field From Mask, and Shaded Material effects to achieve this. And you might have to use a shiny ball rendering as the environment map, like I did. By the way, you can mock up most of this in Core Image Fun House, an application that lives in the Developer directory. Core Image is a great tool to build an imaging application. Just look at Pixelmator!

But How Was This Solved?

Exactly! This was a very interesting problem in constraints. You see, the area outside the text is constrained to be at a height of zero. The area inside the text is initialized to be a height of 1. This is the first image in sequence.

Now blur the text with an 8-pixel radius. It creates softness everywhere, and puts some of the softness outside the text area, because blur actually is something that causes shades to bleed a bit. This is the second image in sequence.

Then you clamp the part outside the text to be zero height again. This recreates a hard edge, and creates the third image in sequence. I have recreated this process in Painter. The clamping was done by pasting in the original mask, choosing a compositing layer method of darken, and dropping the layer, collapsing it back onto the canvas.

Next I take that same image and blur it by a 4-pixel radius. This produces the fourth image in sequence.

I clamp it back to the limits of the original text by pasting, choosing a darken layer method, and dropping, producing the fifth image in sequence.

Notice after the clamp step, the edge remains hard but the inside is becoming more accommodating to the edge, yet remains smooth in its interior.

With the next images in the sequence, I blur with a 2-pixel radius, clamp to the edge of the original mask, then blur with a one pixel radius and clamp to the hard edge of the original mask again to get the final lofted mask.

The last image in sequence is the shaded result, using Apply Surface Texture in Painter.

I should confess that these images are done at a larger scale (3X) and then down sampled for your viewing pleasure. Also, Painter only keeps 8 bits per channel, so the result was a bit coarse, and had to be cleaned up using the softness slider in the Apply Surface Texture effect.

In Core Image, we use more than 8 bits per component and thus have plenty of headroom to create this cool effect at much higher resolution and with fewer artifacts.

It becomes clear that the last several frames of this sequence look practically the same. This is because the blurs are smaller and the effect of the clamping against the edge of the original mask is less prominent. Yet these last steps become very important when the result is shaded as a height field, because the derivatives matter.

Smart People and Hard Problems

It should seem obvious, but it really does take smart people to solve hard problems. And a lot of work. And trial and error. So I'm going to tender a bit of worship to the real brains that helped shepherd me on my way through life and career. To whom I owe so much. And I will explain their influences on me.

The first was Paul Gootherts. Paul is an extra smart guy, and, during high school, Paul taught me the basics of computer programming. He, in turn, got it from his dad, Jerome Gootherts. A competent programmer at 16 (or earlier, I suspect), I owe my livelihood to Paul and his wisdom; he also conveyed to me something that (I think his uncle told him): if you are good at one thing, you can find work. But if you can be good at two things, and apply what you know and cross-pollenate the two fields, then you can be a real success. I applied this to Painter, and almost all of my life. And perhaps someday I'll apply it to music as well. Paul helped me with problems in computation and number theory, and his superb competence led me to develop some of my first algorithms in collaboration with him.

The second was Derrick Lehmer, professor emeritus at UC Berkeley. He taught me that, though education is powerful, knowledge and how you apply it is even more powerful. And it's what you do with your life that is going to make the difference. This has guided me in far-reaching ways I can only begin to guess at. Professor Lehmer ("Don't call me Doctor; that's just an honorary degree") helped me with understanding continued fractions and their application to number theory and showed me that prime numbers and factorization are likely to remain the holy grail of mathematical pursuits. Oh, and his wife Emma (Trotskaia) Lehmer, who was also present, provided many hours of interesting conversation on our common subject: factoring repunits (numbers consisting of only ones). I must credit a few of my more clever number theoretic ideas to her.

Other smart people have also provided a huge amount of inspiration. Tom Hedges had a sharp eye and an insightful mind. He taught me that no problem was beyond solving and he showed me that persistence and a quick mind can help you get to the root of a problem. Even when nobody else can solve it. Tom helped me with Painter and validated so much that I did. Without Tom, it would have been hard to ship Painter at all!

I have probably never met as smart a person as Ben Weiss. When the merger between MetaTools and Fractal Design took place, I became aware of his talents and saw first hand how smart this guy is. He can think of things that I might never think of. He confirmed to me that the power of mathematical analysis is central to solving some of the really knotty problems in computer graphics. And he proceeded to famously solve the problem of making the median filter actually useful to computer graphics: a real breakthrough. I've seen Ben at work since Metacreations, and he is still just as clever.

While Bob Lansdon introduced me to Fourier-domain representation and convolutions, it was really Kok Chen that helped me understand intuitively the truly useful nature of frequency-domain computations. He introduced me to deconvolution and also showed me that there were whole areas of mathematics that I still needed to tap to solve even harder problems. Kok retired a few years back and I sincerely hope he is doing well up north! Kok basically put up with me when I came to Apple and helped me time and time again to solve the early problems that I was constantly being fed by Peter Graffagnino. When it came time to work with the GPU and later with demosaicing, Kok Chen consistently proved to be indispensable in his guidance.

There are plenty other people who I will always refer to as smarter than myself in various areas, but they will have to go unnamed until future posts.

Mess and Creativity

Organization is important. Without it we could never accomplish any task more complicated than tweeting. We all know intuitively when sloppiness works against our productivity. But at what point does organization work against our creative minds?

I hold that some disorganization, some mess, is required to get to a creative point. If a Rubik's cube couldn't be messed up, then it wouldn't be any fun to solve it. In fact, the messed-up Rubik's cube makes a nice symbol for intelligence in disarray.

While the cube provides some exercise for my mind in solving it, it also suggests that we need a mess to get into an analytical state as well. Or at least to practice our analytical side.

But the real value of mixing it up is to be presented with different things in different contexts. We night never put them together if it weren't for the mess in the first place. No, this is not about entropy and order. This is about the interconnectedness of thoughts. The complex relationships, similes, metaphors, and comparisons that our mind makes when presented with diverse options.

Operations on Ideas

One of my fields is imaging: pictures. When developing new imaging technologies, I come across many different techniques that apply to imaging. But the new techniques come from a specific set of operations on ideas that help me to cross disciplines and make something new.

The first operation is deconstruction. With this technique a problem or a subject is torn apart in different ways so we can see what it's made of. With images, this can be something like moving the image into the frequency domain. Or, it can be thinking of the image as a bunch of tiles, or a mosaic. Or re-representing an image as a Gaussian pyramid. You can think of this as the analytical pre-step in being creative. The more ways you can deconstruct something, the more likely you are to find something new.

A sculpture from Napoleon's Arc du Triomphe

Some years ago at Fractal Design I began getting interested in extracting directions from an image: another way to deconstruct an image. This was in order to create a Van Gogh effect, that represented an image using brush strokes that were aligned to the directions of an image.

This is as good a subject as any to introduce the next operation, random association. For something like directions, these associations are concepts like motion, velocity, vectors, maps, routes, paths, going the wrong way, a drunkard's path, alignment, perpendicular, turning the wheel, etc.

The image processed by representing it as directions

These ideas can lead me to look at things that aren't necessarily associated with images, like vector fields, tracing along a direction path, making directions random, canceling the randomness or uncertainty in directions, and other things that seem to be associated with directions.

I use this to help me in branching out, another operation in creative ideation. If I move from directions to vector fields, for instance, I can then look at various properties of vector fields, like vorticity. I can also look at operations that apply to vector fields, like div, grad, and curl that I might never think of when I'm focused solely on images.

Or, looking at direction as a velocity vector can lead me to realize that it has length and angle. Branching out from this can lead me to realize that a direction's angle can be changed. This has dramatic consequences for imaging, since it can lead to an altered reality.

The next creativity operation is experimentation: varying the parameters.

A picture of a tree can be quite picturesque, particularly one from the Kona coast. But when you take the directions in the image and rotate them all 40 degrees counterclockwise and mix them back into the image, you get a windswept alt-tree.

Very different from the original. By both branching out and experimenting, I have created a new effect and it has some profound visual consequences.

It so happens that this effect was accidentally discovered while working on something completely different (which I can't actually talk about)!

I will show few more pictures for the visual people among my readers.

To right you see a picture of me taken about a decade ago near the Statue of Liberty. Here I have applied maybe a fifteen-degree tilt to the directions.

There is a little bit of windswept effect from the direction alteration. This is just what I was going for, and it is fortuitous. With the Arc du Triomphe image, the directions weren't altered in the least. But there is some uncertainty to evaluating directions and, when this effect is applied at a certain scale, you can see that the smallest details aren't always preserved. If they were, it wouldn't be interesting in the least.

Apply this effect to clouds and make the directions perpendicular to their usual course, and you get a puffy, almost feathery, cloud.

It's a jittery, crazy kind of reconstruction of the cloud image.

This brings me to the last operation, which isn't really about creativity, but you can be creative about how you do it, of course: reconstruction. If you have figured out what something is made of, managed to jumble it up internally, then you can reconstruct it and hopefully not end up with Frankenstein.

Can we apply this to another field as well as images? Of course! In music, I deconstruct songs typically so I can reflect on how they are made. Then I can randomly associate the structure of music with, say, grammar. And I can branch out from the usual song grammar to use multiple linking sections, or to precede each verse with a little prelude (I did this in my song Baby, I). Or rearrange the chords backwards and see how that sounds. I did try recording a backwards guitar part in one of my songs, and the interesting process is chronicled in another blog post.

Or, I can deconstruct music into inter weavings of sound and silence. I can put moments of silence into a song, to create a full stop. Perhaps a fake ending, or just a de-textured rest. Yes, I used this in I Know You Know.

I can deconstruct sound into treble, midrange, and bass and create a wall-of-sound interpretation of music. Or deconstruct vocals from instruments. Randomly associating, I can have the vocals play the instrument parts, like the Beach Boys' Brian Wilson had his band do in Help Me, Rhonda.

One of my favorite creativity groups was the Traveling Wilburys. In Handle With Care, they changed the song structure several ways. First off, the song has 2 bridges. Then the solo comes in the fourth verse, and it's only a half-solo. The full solo comes at the end, after the repeat of the two bridges. After the fifth verse.

The Evils of Organization?

While organization is important to our everyday life, too much organization can also hamper us in ideation. The principle is this: if everything is in its own little box, then you simply can't imagine something that is out of the box. Is this even true?

As impossible as it seems, even obsessive-compulsive people can make great artists. This may be because OCD leads to various interesting styles, like horror vacui. Many indications of "madness" in art have drawn us to them in the past. VanGogh and Hieronymous Bosch stand out in my mind.

And there is a place for neat freak artists as well.

But somewhere in between neat freaks and slobs are all the rest of us just trying to be creative and solve problems in a new way. Bringing a fresh approach to something is what it's all about. And disorder (mixing it up) is just one tool to accomplish that goal. Analysis is just as valid, and it is actually necessary for deconstruction.

To properly deconstruct, you need to take a step back and look at your problem in a new way. For instance, looking at texture as geometry instead of pixels. Looking at stuff in different ways is really the true basis of creativity.

Look at this video of the Traveling Wilburys Inside Out. It's just the band playing, but you can see that they took song lyrics and looked at them in different ways. Thanks to the lyrical talents of Bob Dylan and Tom Petty. And the entire subject is inverted again in George Harrison's bridge "be careful where you're walking".

Check out my blog post on Where Do Ideas Come From to see some of these principles in practice, and the value of operating in a creative group, as the Wilburys did.

Texture, Part 4

There are still numerous ways to make textures that have yet to be discussed. One of these, annealing, is particularly visually appealing in a graphic kind of way. In this post, I will discuss the finer nuances of slice-and-dice textures. But first, I think I will show annealing.

To the right you see an annealed texture. The annealing processes based on the technique of simulated annealing. In my interpretation of it, I employ two operations that work against each other iteratively to hone the look of a graphic.

In this case it the first operation is blur. This softens the image. The second operation is increase contrast. This hardens the edges of an image and creates a graphic print look.

As you iteratively apply annealing to an image, it is converted into a graphic representation of that same image, with clean, smooth, rounded black and white areas. With each iteration, the results get a bit smoother, and small features are eliminated also. Simulated annealing comes from metallurgy, where a bit of metal is heated and softened, and then cooled in increments to create different tensile strengths and even crystallization.

In image processing, I have borrowed the term and used it to create a similar process in which an image can be resolved into its most basic forms, and under the control of the user.

For instance, this lacunar image is opened in texture, adjusted 15% lighter, and then it is annealed five times using a small 1.82 pixel blur interleaved with a contrast increase with a slope of about 3.9. You see the five steps in the above example. Obviously, this drastically changes the character of the image.

Now, our task is to use several tricks to create the interesting texture you see at the top of this page (well, at least something a bit like it).

The trick comes from the Fourier transform. An image of spots may be filtered using the Fourier transform and using the spot-shaped filter on the left. This spot is elongated in the frequency domain, and, as I explained in Texture, Part 3, this makes the image spots (in the spatial domain) elongate in the perpendicular direction. Once this is done, the spots lengthen and merge and the result may be filtered with a notch filter to accentuate the spatial frequency that corresponds to the distance between the spots. This process can create stripes, but when you use speckle patterns to seed it, the stripes don't always line up and they create a cool irregular pattern, like the stripes on a zebra or a tiger.

Another technique, called reaction-diffusion, can also generate this kind of pattern.

Anyway, here is an image created using speckle-pattern synthesis and Fourier-domain filtering. The brain looks at this and sees patterns in sand dunes.

Actually, once, on the island of Fanø on the west coast of Jutland, I was driving on the large flat beach they have there. On that particular day, the wind direction and speed was in exactly the same direction and speed that I was driving. This made the patterns in the sand, which were pushed by the wind, become stationary relative to the car. Except that they were still evolving: annealed by the force of the wind, countered by the weight of the sand particles. Patterns soon formed and it was quite an experience, I have to say, to watch them twist and turn, evolving and convolving. The experience only lasted for a few minutes, and it has never occurred again, but I think it might still be made on a computer. I'll look into it.

So, after annealing this pattern, we get a graphic result that matches, but is still different. That's because the pattern does tend to evolve and simplify during the annealing steps.

It is an unusual effect, but I like it.

Though annealing is a metallurgical process, reaction-diffusion is a chemical process, and is readily simulated on a computer. We graphics guys are always looking for new cool-looking techniques to exploit!

And now I think I will exploit speckle patterns some more with some slice-and-dice patterns I made today.

Speckle patterns, like the one you see on the right, are like stippling patterns, but tiling inside the unit square so they can be repeated indefinitely. This works to my advantage, because Texture is used to create these tiling patterns. Like the paper textures in Painter.

In between the spots, you see the Voronoi tessellation. This partitions the tile into cellular areas. Inside each of these cells, we can place some bit of an image. When that image is the same for every cell, you get a very interesting effect.

I placed a bit of light and darkness into each of these cells, using an additive crossfade between each of the cells, and then I softened the result using a slight lowpass filter using the Fourier transform.

The texture I got was like a cellular bump texture, but shaded. You can see it to the left here. I get the shading by offsetting the light area to the lower left of each cell, leaving the darker area to the upper right of each cell.

Then I softened the result to make it appear very physically real and realizable.

Then I did something interesting. I created a speckle with about 150% of the spots, so each cell was smaller. This allowed me considerable play in which shaded portion to place in the cell, since I was using the above image as a source.

I ended up with the image you see to the right. This image is even more physically real, with shadows and catchlights on each cell. And because I used the z-buffer crossfade technique with a very large crossfade width, the edges of each cell are compressed into each other in a novel way, like the seeds on a sunflower.

This technique can make the lines that delineate each cell curved. It's all a function of the z-buffer compositing technique used in merging the cells.

This technique, using a previously sliced-and-diced image as the source for the next one is an iterative technique I used to get more and more complex textures. The trick is deciding which point in the source texture should be used inside all of the cells of the next. It really smacks of genetic programming. I say this because my eye becomes the agent of natural selection as the texture evolves from iteration to iteration.

Today, while making textures, I had a line pattern (which was wavy in one section) and I used that section to slice-and-dice into another texture, using z-buffering to merge the cells.

You can actually see where the fingers of texture interweave into each other on occasion. This is the value of z-buffering over the additive cell merging method: the texture looks more physically real.

Fortunately this technique scales. Here is an example with 5000 stones laid out in a paving stone pattern (or at least a nice pattern). See if you can find the repeat (it's only slightly larger than the amount I have shown).

I'm having way too much fun today!