A few days ago, I found this little gem on the always inspiring WOWGREAT tumbleblog:
Hiroshi Sugimoto, Tyrrhenian Sea (1994); Pixels sorted by Blue.
It was created by Jordan Tate and Adam Tindale by sorting the pixels of this picture. See their site, Lossless processing, for more pixel shuffling goodness.
Adding some randomness
I liked the concept, so I decided to try something similar. But instead of sorting the pixels, I had this vague idea of somehow stirring the pixels in an image, and letting the pixels settle into layers. Or something.
After trying out a few different schemes, I came up with the following procedure:
Pick two pixels from a random column. Swap them if the upper pixel has a higher hue than the lower pixel.
Pick two pixels from a random row. Swap them if the left pixel has a higher saturation (or brightness) than the right pixel.
Repeat the above steps until the image converges.
The first step takes care of the layering of the colors. The second step adds some structure and makes sure the process converges. (If we just swapped two arbitrary pixels, based on the hue, the process would not converge. By swapping pixels column-wise and adding the second step, we impose a global ordering on the image).
Examples
The following are some examples of the method (applied to some photos I took while visiting California recently).
San Diego.
...
Del Mar I.
...
Californian Desert.
...
Del Mar II.
...
And finally, a classic:
Mona Lisa
...
Implementation
The Image Reshuffler was implemented in Processing. It was my first try with Processing, and as I expected it was quite easy to use. Personally, I prefer C++ and Qt, but for someone new to programming, Processing would be an obvious choice.
Quaternions are extensions of the complex numbers with four independent components. Quaternion Julia sets still explore the convergence of the system z ← z2 + c, but this time z and c are allowed to be quaternion-valued numbers. Since quaternions are essentially four-dimensional objects, only a slice (the intersection of the set with a plane) of the quaternion Julia sets is shown.
Quaternion Julia sets would be very time consuming to render if it wasn’t for a very elegant (and surprising) formula, the distance estimator, which for any given point gives you the distance to the closest point on the Julia Set. The distance estimator method was first described in: Ray tracing deterministic 3-D fractals (1989).
My first encounter with Quaternion Julia sets was Inigo Quilez’ amazing Kindernoiser demo which packed a complete renderer with ambient occlusion into a 4K executable. It also used the distance estimator method and GPU based acceleration. If you haven’t visited Quilez’ site be sure to do so. It is filled with impressive demos, and well-written tech articles.
In the 1989 Quaternion Julia set paper, the authors produced their images on an AT&T Pixel Machine, with 64 CPU’s each running at 10 megaFLOPS. I suspect that this was an insanely expensive machine at the time. For comparison, the relatively modest NVIDIA GeForce 8400M GS in my laptop has a theoretical maximum processing rate of 38 gigaFLOPS, or approximately 60 times that of the Pixel Machine. A one megapixel image took the authors of the 1989 paper 1 hour to generate, whereas Subblues GPU implementation uses ca. 1 second on my laptop (making it much more efficient than what would have been expected from the FLOPS ratio).
GPU Acceleration and the future.
These days there is a lot of talk about using GPUs for general purpose programming. The first attempts to use GPUs to speed up general calculations relied on tricks such as using pixel shaders to perform calculations on data stored in texture memory, but since then several API’s have been introduced to make it easier to program the GPUs.
NVIDIAs CUDA is currently by far the most popular and documented API, but it is for NVIDIA only. Their gallery of applications demonstrates the diversity of how GPU calculations can be used. AMD/ATIs has their competing Stream API (formerly called Close To Metal) but don’t bet on this one – I’m pretty sure it is almost abandoned already. Update: as pointed out in the comments, the new ATI Stream 2.0 SDK will include ATIs OpenCL implemention, which for all I can tell is here to stay. What I meant to say was, that I don’t think ATIs earlier attempts at creating a GPU programming interface (including the Brook+ language) are likely to catch on.
Far more important is the emerging OpenCL standard (which is being promoted in Apples Snow Leopard, and is likely to become a de facto standard). Just as OpenGL, it is managed by the Khronos group. OpenCL was originally developed by Apple, and they still own the trademark, which is probably why Microsoft has chosen to promote their own API, DirectCompute. My guess is that CUDA and Brook+ will slowly fade away, as both OpenCL and DirectCompute will come to co-exist just the same way as OpenGL and Direct3D do.
For cross-platform development OpenCL is therefore the most interesting choice, and I’m hoping to see NVIDIA and AMD/ATI release public drivers for Windows as soon as possible (as of now they are in closed beta versions).
GPU acceleration could be very interesting from a generative art perspective, since it suddenly becomes possible to perform advanced visualization, such as ray-tracing, in real-time.
A final comment: a few days ago I found this quaternion Julia set GPU implementation for the iPhone 3GS using OpenGL ES 2.0 programmable shaders. I think this demonstrates the sophistication of the iPhone hardware and software platform – both that a hand-held device even has a programmable GPU, but also that the SDK is flexible enough to make it possible to access it.
In July Subblue released another Pixel Blender plugin, called the Fractal Explorer Plugin – for exploring Julia sets and fractal orbit maps. I didn’t get around to try it out until recently, but it is really a great tool for exploring fractals.
Most people have probably seen examples of Julia and Mandelbrot sets – where the convergence properties of the series generated by repeated application of a complex-valued function is investigated.
The most well-known example is the iteration of the function z ← z2+c. The Mandelbrot set is created by plotting the convergence rate for this function while c varies over the complex plane. Likewise, the Julia set is created for a fixed c while varying the initial z-value over the complex plane.
Glynn1 by Subblue (A Julia-set where an exponent of 1.5 is used).
Where ordinary Julia and Mandelbrot sets only take into account whether the series created by the iterated function tends towards infinity (diverges) or not, fractal orbits instead uses another image as input, and checks whether the complex number series generated by the function hits a (non-transparent) pixel in the source image. This allows for some very fascinating ‘fractalization’ of existing images.
A fractal orbit showing a highly non-linear transformation of a Mondrian picture.
Subblue suggests starting out using Ernst Haeckel beautiful illustrations from the book Artforms of Nature, and he has put up a small gallery with some great examples: An example of an orbit mapped Ernst Haeckel image.
To try out Subblue’s filter, download the Pixel Blender SDK and load his kernel filter and an input image of choice. It is necessary to uncheck the “Build | Turn On Flash Player Warnings and Errors” menu item in order to start the plugin. On my computer I also often experience that the Pixel Blender SDK is unable to detect and initialize my GPU – it sometimes help to close other programs and restart the application. The filter executes extremely fast on the GPU – often with more than 100 frames per second, making it easy to interactively explore and discover the fractals.
As I final note, I implemented a fractal drawings routine myself in Structure Synth (version 1.0) just for fun. It is implemented as a hidden easter egg, and not documented at all, but the code belows shows an example of how to invoke it:
Arguable, this code is not very optimized (it is possible to add an unlimited number of terms, making the function evaluation somewhat slow), but still it takes seconds to calculate an image making it more than a hundred times slower than the Pixel Blender GPU solution.
Once again I’m extremely impressed by what shows up on the demoscene.
Slisesix - Generative Art in 4K
Inigo Quilez managed to create the following picture within a 4KB executable. In fact he managed to fit a renderer and the generative code for both the scene and the textures in only 3900 bytes.
The Demo Scene never cease to amaze me. The technical quality of these demos is amazing – complex 3D scenes rendered real-time, procedural textures, real-time sound synthesis, and incredible low foot-prints.
Recently I stumbled upon demoscene.tv which features recorded videos (flash video) of many of the best demos. Of course part of the fun is actually running these demos, to be amazed that they are indeed real-time, but sadly my laptop is not geared towards neither CPU or GPU intensive activities.
San Diego.
Del Mar I.
Californian Desert.
Del Mar II.
Mona Lisa
