subblue

4D Quaternion Julia Set Ray Tracer

Sat, 19 Sep 2009 23:00:00 GMT

A quaternion Julia set is a four-dimensional equivalent of the standard two-dimensional fractal. By taking a 3D 'slice' through the 4D space it is possible to visualise a solid fractal.

This quaternion Julia set ray tracer is a port of Keenan Crane's Cg GPU implementation for Adobe Pixel Bender and a more general GLSL shader patch for Quartz Composer. The Pixel Bender version lets you render out high resolution images in Photoshop CS4 (or animate the parameters in After Effects). The Quartz Composer patch lets you animate any parameter in real-time.

The maths bit

Complex numbers have two components that define a point in a plane and are the core build blocks of fractal calculations. In 1843 the Irish mathematician Sir William Rowan Hamilton developed quaternions as a way of describing complex points in three-dimensional space. The only snag was he had to add a fourth dimension to make the maths work (hence the quad part of the name). Whilst complex numbers are described as the sum of a real and imaginary component: z = a + bi, quaternions are similar but have three imaginary components: z = a + bi + cj + dk

Fractals can be calculated using quaternions with the usual equation z_n+1 = z_n² + c where we track which points have a magnitude greater than the bailout threshold. The problem is trying to visualise the set of 4D points in 3D space. At this point I'll direct you to an excellent write-up Keenan has posted that describes the process in detail.

The ray tracing bit

The ray tracing is actually more like the ray-marching process I used in the procedural terrain renderer; a ray vector is fired into the scene and stepped forward until it gets within a collision threshold of the fractal. This brute-force approach is very inefficient but fortunately there are couple of optimisations that can be taken advantage of.

Firstly, a bounding sphere is defined as the limit of the fractal and used as the starting point for the initial ray vector for each pixel. This removes any unnecessary stepping at the start.

Secondly, there is a distance estimator function that will return the distance to the closest point on the Julia set for any z point in quaternion space. The distance estimator accelerates the ray tracing by a method called unbounding volumes, described in the paper Ray Tracing Deterministic 3-D Fractals [John Hart et al, 1989]. At each point of the rays journey through quaternion space the distance estimator returns the distance to the closest point in the Julia set. It means the next step the ray takes can be of this amount, which greatly reduces the overall number of steps required to intersect the fractal surface.

When the ray comes within a defined collision distance, epsilon, of the fractal surface the ray marching is stopped. Note, a fractal has an infinite level of detail so the epsilon factor acts to smooth out the surface and make it renderable.

The normal vector for each point is generated from the gradient of the approximate fractal surface. The full technique is described in the paper mentioned above.

Shading and ambient occlusion

My contribution with this shader is the addition of a basic ambient occlusion (AO) parameter. AO darkens areas of a surface that are in close proximity and less likely to receive light from its surroundings. When combined with standard shading, ambient occlusion gives a far more realistic looking image.

AO has been applied to quaternion Julia set fractals before by Inigo Quilez and animated here. However, these implementations are quite involved requiring multiple passes and extra sampling. The implementation used in this ray tracer is just an approximation and not physically accurate, but does add a visual improvement at very little additional computational cost.

Simply darken the surface by a factor proportional to the number of ray tracing steps taken for each point and the result is comparable to ambient occlusion. It works thanks to a side effect of the unbounded volume ray tracing approach; points that are least occluded are likely to be reached in fewer steps as the distance estimator function will return a large step size for the ray. Whereas rays to points nested in creases or dips will require more steps because the neighbouring surfaces will cause the distance estimator to return a smaller step size.

The image below illustrates the different components that makes up the final surface. Top row, left to right: pure ambient occlusion, pure phong. Bottom row: ambient occlusion and phong combined, and finally everything; a base colour with specular highlights and ray traced shadows.

Download and installation

Download the Quaternion Julia set ray tracer

For Pixel Bender open the QuaternionJulia.pbk file with the Adobe Pixel Bender Toolkit or copy it into the Pixel Bender Files folder in your Photoshop CS4 installation directory (you will need to have installed the PB plugin for Photoshop first).

The Quartz Composer patch was created with Quartz Composer 4, which is part of the new XCode. It will also work with QC3 as the patch is just a GLSL shader. I've had it running without antialising at up to 30fps @ 600x400 on my iMac with an NVIDIA GeForce 8800GS.

Just after porting this to Quartz Composer I discovered that Apple have released an OpenCL implementation for Snow Leopard. With native support now built into Snow Leopard, OpenCL opens up some very exciting possibilities for future projects.

Artforms of Nature

Fri, 17 Jul 2009 23:00:00 GMT

The nineteen century German biologist Ernst Haeckel is famous for his fantastically illustrated book Artforms of Nature. The copyright for this book from 1904 has now expired and thanks to Wikimedia Commons it is available for everyone to appreciate.

Haekel's artistic interpretation of the biological forms he studied have a clarity of symmetry and detail that has been a source of inspiration for many artists and engineers over the years. They provide the perfect subject matter for the Fractal Explorer plugin.

Astrophyton darwinium:

All images here are released under a Creative Commons Attribution-Noncommercial-Share Alike license.

Fractal Explorer Pixel Bender Plugin

Mon, 13 Jul 2009 23:00:00 GMT

A new Pixel Bender plugin for generating a wide variety of fractals in real-time. A key feature enables images to be mapped into fractal space creating some amazing results.

Head over to the Fractal Explorer project page to download the plugin and find out more.

The above image is licensed under the Creative Commons Share Alike-Attribution-Non-Commercial license as per the original thanks to Audringje.

Fractals and generative art resources

Wed, 13 May 2009 23:00:00 GMT

As a follow up to my talk on Fractals and Generative Art at the Apple Store in Glasgow here is a list of links for further reading and exploration.

The mathematics of fractals

Good places to start learning about the mathematics of fractals are Wikipedia and Mathworld. There are many books on the subject but three books I can recommend are Chaos and Fractals - New Frontiers of Science, The Computational Beauty of Nature and the definitive work by Mandelbrot, The Fractal Geometry of Nature.

Fractal generation

Ultrafractal is the Photoshop of the fractal world. It's Windows only but works very nicely via Parallels on the Mac. Other programs worth investigating is the open-source GNU Xaos and the Mac only Quadrium apps.
Writing your own fractal rendering scripts is highly recommended as a good way to explore the subject.

Fractal explorer is the Pixel Bender plugin for Photoshop and After Effects CS4 that I demonstrated in the talk. I'm making some final tweaks and will be releasing it soon!

Fractal Flames

Fractals flames are a form of Iterative Functional Systems (IFS). To find out more see flam3.com. Apophysis is the daddy of this area. Mac users have to use the Java port, Apophysis-j. The open-source programme can take a bit of effort to get interesting results but these tutorials will help you on your way. The Apophysis group on deviantART is a great place to see what is possible.

I also recommend the excellent Electric Sheep animated fractal flame screen saver - keeps you tripping for hours.

Context Free

Context Free is an open-source programme for visualising Context Free Design Grammars (CFDG) and is an excellent tool for exploring generative graphics. The images are rendered from a set of simple recursive rules that can often create surprising beautiful results. Try out some of the code examples in the gallery for a quick start.

Structure Synth

Taking CFDG into the third dimension, Structure Synth is a fantastic open-source tool for creating abstract 3D models. There are some good example scenes included to get you started and an active Flickr group to feed your inspiration.

Sunflow

Sunflow is an open-source global illumination rendering system written in Java. There hasn't been a new release of the programme in a couple of years, but it is already a very capable system. Structure Synth can export Sunflow scenes and it has plugins to integrate with the open-source 3D package Blender.

TopMod

TopMod is a specialist open-source 3D topology modelling tool with support for Python scripting. It's not really a tool for pure generative graphics but damn cool all the same!

Terragen

Terragen is an amazing photo-realistic landscape and environment renderer. Its fractal based terrain generator enables you to create entire worlds procedurally. There is a resolution limited free version you can use for non-commercial projects to get started with.

Flash, Flex, Actionscript 3.0, Pixel Bender and friends

Adobe Flash is one of the best ways to share your visualisations and the power of Actionscript 3.0, especially combined with Pixel Bender and Alchemy, has enabled some pretty impressive stuff. You also don't need the full Adobe Flash IDE to create Flash apps. See the Adobe open-source site for more information.

The Pixel Bender exchange is a good source for example scripts. Also keep your eye on the Adobe Labs site as there is always cool stuff going on. See the Droste effect plugin project page to get started.

Processing

Processing is an open-source Java based programming language and environment for generating images, animations and visualisations. It is one of the biggest players in the generative graphics scene with a huge community, many online resources and a number of books on the subject.

Nodebox

Nodebox is a Mac only graphics programming environment very similar to Processing but based on Python. Although it might have a much smaller community than Processing it still has a very complete selection of libraries and can generate extremely high quality images and animations.

Open frameworks

Open Frameworks is another visual programming environment, this time based on C++. See the forum and wiki for more information.

Blogs and places of inspiration

There are a huge number of blogs and sites focusing on generative graphics by many extremely talented people. A few to get you started:
Generator.x
Data is Nature
Flight 404
Daniel Shiffman
Dave Bollinger
BIT-101
Dr. Woohoo!
Quasimondo
Memo.tv
Soulwire
W:Blut
Information Aestetics
Visual Complexity

Credits

Specific thanks to Chris Creek and Sven Fauth for letting me use a couple of their Apophysis images in the presentation and Michael Hogg for sharing his Mandelbrot deep zoom animation.

A preview of my new Pixel Bender fractal explorer plugin - see the new project page.

Fractals and generative art talk

Sat, 09 May 2009 23:00:00 GMT

6pm on Thursday 14th May at the Apple Store in Glasgow.

I'm going to be talking about creating fractals and generative art on the Mac. I'll be focussing on demonstrating some of the many open-source apps and scripts freely available. There will be lots of pretty pictures and animations and no mathematical or programming experience will be required.

Hopefully it will sow a few seeds for the curious to go away and explore the world of fractal and generative art themselves.

A write-up is now online.

Tracing a terrain

Sat, 07 Mar 2009 00:00:00 GMT

This is a basic terrain rendering filter for Pixel Bender based on the Quasi-Analytic Error-Bound (QAEB, or "kweeb") ray tracing algorithm.

QAEB tracing is a raymarching algorithm for rendering realistic looking terrains using procedural fractal functions first introduced by Ken Musgrave. After reading the chapter about it in the excellent book, "Texturing & Modeling: A Procedural Approach", I thought it might make an interesting challenge for an interactive Pixel Bender filter.

The process is fairly unsubtle; a ray vector for each pixel is fired into the scene and its offset, y, above a 2D height field, f(x, z), is calculated. The ray is repeatedly stepped, or marched, forward until it intersects the terrain. At this point the colour for the pixel is determined based on its calculated height and angle between the surface normal-vector and sun position. A secondary ray can be fired off from the intersection point towards the sun and if it intersects the terrain again we know that the original surface point must be in shadow.

A couple of optimisations can be used to speed up the rendering. Firstly the step interval can be increased proportionally with distance as the geometric details get smaller in screen space the deeper into the scene. The second optimisation requires the scene to be rendered from the bottom up (near to far). It uses the calculated scene depth of the pixel below the one we want to calculate as the starting point for its ray as we know that as we move up the image we go deeper into the scene. However, Pixel Bender calculates many pixels in parallel on the GPU and so you can't use the result of one pixel calculation as the starting point for another, which unfortunately means we can't take advantage of this second optimisation.

This filter uses a composition of sinusoidal functions at different frequencies to generate the height map. It's by no means perfect but at a low altitude gives a reasonable cartoon-like landscape where the repeating structure isn't obvious. I created a different version that used Perlin noise for the height field, which generated a much more realistic terrain but would cripple Pixel Bender causing a few hard reboots! I'm porting this version to Processing and will post about that soon.

Other features such as the water level are set by clipping the height field at a lower limit and building like structures can be generated using a combination of modulo functions. There is also an option to overlay contour lines on the terrain.

For more technical details on terrain rendering and other excellent computer graphics goodies see Inigo Quilez's site.

Download the Landscape PixelBender filter
See the Adobe PixelBender page for instructions on using the filters with Photoshop CS4 and After Effects

Escher's Droste Effect

Mon, 17 Nov 2008 00:00:00 GMT

The "Droste effect" derives from a Dutch chocolate maker that used an image of its box on the box recursively at smaller and smaller scales.

MC Escher's "Prentententoonstelling" (print gallery) image took this idea one step further and mapped the image on itself in a spiral. However, he only got so far with pen and paper leaving an enigmatic white centre. It wasn't until the Dutch mathematician, Hendrik Lenstra, worked out the maths behind the image transformation that the complete effect could be visualised. Take a look at the illustrated write-up that gives a good explanation about the process.

Jos Leys took the process further and created a generic logrithmic image transformation that can create endless zooming animations. This process was turned into a Mathmap script by Josh Sommers and Briec and now has an active Flickr group that use it.

I've ported the Mathmap script over to Adobe's new Pixel Bender Toolkit. Pixel Bender was officially released as part of the CS4 suite but is also available as a free download. The filters will run in After Effects, Photoshop CS4 and Flash 10 (in some cases) so there is huge creative potential here!

See the project page for download and usage instructions

Fast Mandelbrot Renderer

Thu, 13 Nov 2008 00:00:00 GMT

Here is another version of the classic Mandelbrot set, however this one runs fast enough in Pixel Bender for real-time zooming all the way down to the limit of the floating point number precision (at which point you get some glitchy goodness).

Adobe recently launched the Pixel Bender Toolkit, which is a high-performance graphics processing language for image processing. It will offload the image processing to the GPU enabling very high performance operations.

You will need to install the Pixel Bender Toolkit (available as a free download here) and then copy & paste in the code below.

Some pixel bender scripts can be compiled into filters than can be used within Flash 10 applications. However, Flash doesn't yet support filters with loops like this one, so we won't have a super-charged Flash fractal explorer just yet.

/**
 * Mandelbrot.pbk
 * 
 * Copyright (c) 2008 Tom Beddard
 * http://www.subblue.com
 * 
 * Licensed under the MIT License: http://www.opensource.org/licenses/mit-license.php
 * 
 * 
 * Tips:
 * - Use the centerPreset option to jump to interesting parts of the Mandelbrot set.
 * - Increase the maxIterations option to increase detail on high zooms.
 * 
 * As loops aren't supported with Hydra code it curently isn't possible to export this
 * for use in Flash. 
 */

<languageVersion: 1.0;>

kernel Mandelbrot
<   namespace : "com.subblue.filters";
    vendor : "Tom Beddard";
    version : 1;
    description : "Mandelbrot set renderer";
>

#define BAILOUT 10.0

{
    output pixel4 dst;
    
    parameter int2 size
    <
        minValue:int2(100, 100);
        maxValue:int2(1000, 1000);
        defaultValue:int2(640, 480);
    >;
    
    parameter float2 center
    <
        minValue:float2(-2.0, -1.0);
        maxValue:float2(2.0, 1.0);
        defaultValue:float2(-0.5, 0.0);
    >;
    
    parameter float2 centerOffset
    <
        minValue:float2(-1.0, -1.0);
        maxValue:float2(1.0, 1.0);
        defaultValue:float2(0.0, 0.0);
    >;
    
    parameter int centerPreset
    <
        minValue:0;
        maxValue:4;
        defaultValue:0;
    >;
    
    parameter float zoomMajor
    <
        minValue:0.0;
        maxValue:20.0;
        defaultValue:0.0;
    >;
    
    parameter float zoomMinor
    <
        minValue:0.0;
        maxValue:10.0;
        defaultValue:0.0;
    >;
    
    parameter int maxIterations
    <
        minValue:20;
        maxValue:800;
        defaultValue:200;
    >;
    
    region generated()
    {
        return region(float4(0, 0, size.x, size.y));
    }
    
    void
    evaluatePixel()
    {
        pixel4 p;
        float aa, bb, zz, twoab;
        float x0 = center.x;
        float y0 = center.y;
        
        // Use a center preset to find some nice parts of the Mandelbrot set
        if (centerPreset == 1) {
            x0 = -0.742522478103764;
            y0 = -0.143708014488453;
        } else if (centerPreset == 2) {
            x0 = 0.36295341867850555;
            y0 = -0.6455617463848476;
        } else if (centerPreset == 3) {
            x0 = 0.3218759918211005;
            y0 = 0.03518083572368085;
        } else if (centerPreset == 4) {
            x0 = -1.673497088962531;
            y0 = -0.0003318667941149705;
        }
        
        float zoom = exp(zoomMajor + zoomMinor);
        float x1 = x0 - 2.0 / zoom;			// Left limit of x
        float x2 = x0 + 2.0 / zoom;			// Right limit of x
        
        float spanX = x2 - x1;
        float spanY = spanX * (float(size.y) / float(size.x));
        float y1 = y0 - spanY / 2.0;
        float y2 = y0 + spanY / 2.0;
        
        x1 += centerOffset.x * spanX;       // Shift centre for fine tuning of position
        y1 += centerOffset.y * spanY;
        
        float2 z = float2(x1, y1) + outCoord() * float2(spanX / float(size.x), spanY / float(size.y));
        float2 z0 = z;
        int n = 0;
        
        dst = pixel4(0.0, 0.0, 0.0, 1.0);   // Set everything to black first
        
        /**
		 *  Mandelbrot formula
		 *	z' = z^2 + c
		 *	 where: z = a + bi
		 *		    z^2 = (a^2 - b^2) + (2ab)i
		 *	 and: c = x + yi
		 */
        while (n < maxIterations) {
            aa = z.x * z.x;
            bb = z.y * z.y;
            
            if (aa + bb > BAILOUT) {
                // Fill the pixel based on the time it takes to reach the bailout threshold
                p = pixel4(1.0 - float(n) / float(maxIterations));
                p.a = 1.0;
                dst = p;
                break;
            }
            
            twoab = 2.0 * z.x * z.y;
            z.x = aa - bb + z0.x;
			z.y = twoab + z0.y;
            n += 1;
        }
    }
}

Butterfly curves

Wed, 05 Nov 2008 00:00:00 GMT

Taken from Clifford Pickover's book, Computers and the Imagination, is this experiment that creates butterfly like curves.

The formula is expressed in polar coordinates as:

By changing the A, B, a, b and c parameters you can get some nice results.
Click on the image below to give it a go.

Guilloch� Patterns

Thu, 09 Oct 2008 23:00:00 GMT

If you wanted to design your own bank notes or passport you might consider using a Guilloché pattern as one of your anti-counterfeiting measures.

I first heard about Guilloché patterns in a recent post over at the Ministry of Type blog run by Aegir Hallmundur. Guilloché machines (also known as geometric lathes) have been used since the 17th century by watchmakers and goldsmiths, such as Fabergè, for for ornamentation.

Using the set of Hypotrochoid equations Aegir describes I've built a little Flash app to experiment with the various parameters. Click the picture below to play.

Download the AS3 source code and play with the Guilloché explorer.