Experimentalized

Recursive Random Triangular Subdivision

2012-01-12T08:51:00.001-08:00

I've started getting into writing my blog on my lunch hour so I've had to come up with some quick and easy 30 minute experiments - I need the other 30 minutes to eat... Here is today's result (it follows along the lines of my circle packing experiment a while back). It works like this. One starts by drawing a triangle, then picks a random point within that triangle. These vertices are then used to draw more triangles, and the process is repeated recursively. At each stage the triangles are rendered with a level of transparency. This means more "visited" triangles will appear brighter thus forming a kind of network. Click the image below to launch the demo and find the source here.

Embedding Fonts In Actionscript 3

2012-01-11T05:56:00.000-08:00

I hardly use the Flash IDE at all any more. Pretty much all of my coding is done in FlashDevelop. One thing that the IDE does very well is the embedding of fonts but there are certainly ways of doing it using purely code. People seem to have found many ways of embedding fonts but this one has always worked for me:

This class is my font library - I embed all fonts that I use in here. The two things to note are the embed code for the fonts and public constants to allow me to access them using FontLibrary.FONT...

package org.experimentalized.fonts 
{
 /**
  * Font Library
  * @author Experimentalized
  */
 public class FontLibrary 
 {
  //Embed your fonts here
  [Embed(source="samplefont.ttf",fontName = "Mia's Scriblings ~", mimeType = "application/x-font-truetype")]
  private static const _samplefont:String;
  
  //Access font using this
  public static const FONT_SAMPLE:String = "Mia's Scriblings ~";
 }
}

This is the main class of my application. Here I create a sample text field and set the text format to one of my embedded fonts.

package org.experimentalized.fonts 
{
 import flash.display.Sprite;
 import flash.text.TextField;
 import flash.text.TextFormat;
 
 public class Fonts_Demo extends Sprite 
 {  
  public function Fonts_Demo() 
  {
   //Create a new text field
   var text_field:TextField = new TextField();
   text_field.width = 500;
   text_field.height = 200;
   
   //Make sure we embed fonts
   text_field.embedFonts = true;
   
   //Create some text
   text_field.text = "This is a test";
      
   //Set the font using our new font library
   text_field.setTextFormat(new TextFormat(FontLibrary.FONT_SAMPLE, 30));
   
   //Add the text field to the display object list
   addChild(text_field);
  } 
 }
}

Easy! You can download all of the source files for this and my other projects from: http://experimentalized.com/blog/sourcezip/Blog.zip.

Two Dimensional Water Simulation

2012-01-11T05:24:00.000-08:00

This is my first blog post in a while so I thought I'd try something interesting. A few years ago I took a look at some discrete cell methods for simulating water in 2D. I decided to take a new approach and use a particle based method to simulate particles interacting. The image below shows the simulation running with 6000 particles at a reasonable framerate. All the particles in the scene repulse one another, and are accelerated earthward by gravity. If a naive approach were taken, the number of tests performed on each iteration of the program would be 6000 * 6000 = 3600000 distance calculations. This would be a large number of square roots for even the best CPU. In order to get around this I make use of some simple image filters to approximate the same result. Each particle is rendered to a bitmap buffer as a single pixel (I took this approach for a previous experiment). These pixel values are then blurred and the gradients at each point on the bitmap calculated using Sobel operators. At this stage calculating particles updated trajectories is just a case of subtracting the value of the gradient at each point from their velocity. Because the blur filter naturally falls off the repulsive force is proportional to the kernal used in the filtering process.

As usual just click to try out the demo!

The source code for all projects from now on will be added to a single flash project which can be found at:

http://experimentalized.com/blog/sourcezip/Blog.zip

Voice Recognition in Flash

2011-08-08T13:55:00.000-07:00

This evening I thought I'd take a crack at looking at voice recognition in flash. The idea for this came after the realisation that when using my phone I have almost entirely given up on using the keypad. Instead I simply utter a few words (When passers by are out of ear shot) and a voice appears at the other end. Wonderful! I haven't read up on voice recognition at all so in part I am using the knowledge I've gained by looking at image recognition and tracking software. Being a big Aphex Twin fan and having written a spectrograph to visualize this song in flash before I had at least a bit of a grounding. The idea would be to record a small sample of voice, using some microphone thresholding, draw a spectograph of the sample and then compare the spectograph to a database of possible patterns and determine which command or whatever is most similar. I'm pleased to say that I have completed the first half of this today and you can click to see a demo below (The top image will launch it):

The images are of a whistling sequence, a glass being rung, and me saying hello. Interestingly you can see the harmonics of the glass being rung (a few set frequencies). My voice is a bit harder to translate but using some analysis I'm sure it will be possible.

Anyway as usual the source code can be downloaded here and let me know if you come up with anything using it. How about auto-tuning?!

The plan from here is to save single voice clips as images, and train a neural network to find patterns in both the volume and the spectograph for a set number of commands. I will report my findings shortly!

Perceptron in Actionscript

2011-07-16T15:42:00.000-07:00

I've always thought neural networks and the idea of computational learning was pretty cool but until now I'd never actually tried to program one. I decided to start out with something simple so I went for the single layer perceptron with the hope of building it up to something a bit smarter.

For those of you who don't know much about neural networks Wikipedia has done a pretty decent job in teaching me everything I know. All the project files are available here and sample source code is provided below. It is a simple solution to the NAND problem using two inputs.

The perceptron class essentially has two functions, train and evaluate. The train function is called 100 times on the training set which adjusts the respective weights on each input. When evaluate is called on a particular inputs an output is produced. The output trace from the below program looks like this:
Initiating new perceptron:

Training 100 times using training set...

Trained

Evaluating NAND[0,0] : 1

Evaluating NAND[1,0] : 1

Evaluating NAND[0,1] : 1

Evaluating NAND[1,1] : 0

This is a fast solution to these kinds of problems. I plan on implementing optimisations such as exiting training when the weights change by less than some threshold (i.e the solution limit has been reached), but the end goal is to produce a full library with many kinds of next step. I think the next of these will be a multilayer perceptron which initial research suggests is much more complicated! Enjoy the classes and let me know if you do anything interesting with them.

package

{

import flash.display.Sprite;

import org.experimentalized.networks.SingleLayerPerceptron;

import org.experimentalized.networks.objects.Trainer;

import org.experimentalized.networks.objects.TrainerSet;

public class Main extends Sprite

{

public function Main()

{

//NAND example

trace("Initiating new perceptron:");

var perceptron:SingleLayerPerceptron = new SingleLayerPerceptron(0.1);

var training_set:TrainerSet = new TrainerSet([ new Trainer([0,0],1),

new Trainer([1,0],1),

new Trainer([0,1],1),

new Trainer([1,1],0)

]);

trace("Training 100 times using training set...");

perceptron.TrainSet(training_set,100);

trace("Trained");

//Test some evaluations

trace("Evaluating NAND[0,0] :",perceptron.Evaluate([1,0]));

trace("Evaluating NAND[1,0] :",perceptron.Evaluate([1,0]));

trace("Evaluating NAND[0,1] :",perceptron.Evaluate([0,1]));

trace("Evaluating NAND[1,1] :",perceptron.Evaluate([1,1]));

}

Colour Wheel - HSV Colour Space

2011-07-07T10:47:00.000-07:00

I've just been playing around with colour wheels and colour representation in flash. I had a think about whether it was possible to represent every single colour in the RGB spectrum on a single 2D image. Closer inspection reveals that it isn't possible because RGB is made up of three components - red, green and blue - and therefore needs three dimensions. This is why if you look up different colour representations on Wikipedia you might see them represented by cones, or cubes. I decided to work in the HSV colour space which is formed of Hue (rotation), Saturation (The amount of colour compared to black/white) and Value (Essentially the brightness). The resulting colour wheel can be seen below:

Just click on the image to launch the app. By rolling over the wheel the colour in the box will show the selected colour. Use the up/down arrow keys to alter the "V" value of the wheel. This should allow you to view a complete (discrete) representation of every colour in the RGB spectrum.

If you're interested in source code just click here to download the FlashBuilder project and AS files. Enjoy!

There's nothing boring about Tax!

2011-06-28T13:20:00.000-07:00

Well the title might be a bit misleading, but I'll let you be the judge of that. A close friend and I were in the pub last week discussing the benefits of a tax system which, instead of being tiered, would be characterised by a continuous curve. My friend being an Economist, and me a Physicist, and both of us slightly tipsy thought that we might be able to change the world with our new theory - so I went home that night and wrote a small program using FlashMath to try and quantify some of our ideas. The program essentially integrated over a Cauchy-Schwartz curve and compared collected tax with that of the standard tiered system. I had planned on expanding on this by optimising the curve using measures such as utility (an economic measure of happiness of a population) but for now here is the source code:

package org.experimentalized
{
 package
{
 import flash.display.MovieClip;
 import com.experimentalized.math.quadrature.SimpsonsQuadrature;

 public class Tax extends MovieClip
 {
  private var gamma:Number = 7000;
  private var x0:Number = 22000;
  private var population:Number = 65000000;
  
  private var gamma2:Number = 12000;
  private var x1:Number = 30000;
  private var beta:Number = 0.52;
  
  public function Tax()
  {   
   trace(calculate_total_teired_tax_collected(1000000));
   trace(calculate_total_new_tax_collected(1000000));
  }
  
  public function calculate_total_new_tax_collected(Limit:Number):Number
  {
   var S:SimpsonsQuadrature = new SimpsonsQuadrature(new_tax_proportion,0,Limit,100);
   return S.integrate();
  }
  
  public function new_tax_proportion(X:Number):Number
  {
   return population*calculate_new_tax_collected(X)*evaluate_income_percentile(X);
  }
  
  public function calculate_new_tax_collected(income:Number):Number
  {
   var S:SimpsonsQuadrature = new SimpsonsQuadrature(lorenzian_cdf,0,income+0.001,100);
   return S.integrate();
  }
  
  public function lorenzian_cdf(X:Number):Number
  {
   return (1/Math.PI)*Math.atan((X-x1)/gamma2)*beta + beta/2;
  }
  
  public function calculate_total_teired_tax_collected(Limit:Number):Number
  {
   var S:SimpsonsQuadrature = new SimpsonsQuadrature(teired_tax_proportion,0,Limit,100);
   return S.integrate();
  }
   
  public function teired_tax_proportion(X:Number):Number
  {
   return population*calculate_teired_tax_collected(X)*evaluate_income_percentile(X);
  }
  
  public function calculate_teired_tax_collected(income:Number):Number
  {
   var taxable:Number = income - 7475;
   if(income>100000) taxable = income;
   
   var basic_rate:Number = taxable;
   if(basic_rate>35000) basic_rate = 35000;
   
   taxable = taxable - basic_rate;
   
   var higher_rate:Number = taxable;
   if(higher_rate>115000) higher_rate = 115000;
   
   taxable = taxable - higher_rate;
   
   var additional_rate:Number = taxable;   
   
   if(basic_rate<0) basic_rate = 0;
   if(higher_rate<0) higher_rate = 0;
   if(additional_rate<0) additional_rate = 0;
   
   return basic_rate * 0.2 + higher_rate * 0.4 + additional_rate * 0.5;
  }
    
  public function evaluate_income_percentile(X:Number):Number
  {
   //Model as lorenzian
   return (1/Math.PI)*(gamma/((X-x0)*(X-x0) + gamma*gamma))   
  }
 }
}

It isn't commented in the slightest but see what you can make out of it!

iPhone Location Data

2011-05-04T11:57:00.000-07:00

For those of you who haven't yet heard, Apple are tracking your every move. As somebody who has nothing to hide ( hopefully ), I thought I'd share an experiment I'd carried out using some of my own location data and OpenHeatMap. Apple store triangulated data based on nearby cell masts and not based on GPS which is a slight shame because the accuracy isn't great. Here is a greatly speeded up video of my actions since December 2010.

Aerodynamics for Convex Hulls

2011-04-25T09:04:00.000-07:00

I had quite a nice thought experiment and thought I'd document it for you guys to have a look at. I wanted to come up with a quick way to (semi) realistically simulate lift and drag on any shape. Such an engine could be used for flash games for example a hang glider game. Realism like this (if carefully implemented) can add a lot to a game.

I plan on implementing this in flash sometime after my exams are over, but some of you might be interested in my approach, so feel free to beat me to coding it!

Here is what I've got so far, you can click on a page to expand it in a lightbox (or click here to download the pdf):

Fun with Inverse Kinematics

2011-04-25T06:50:00.000-07:00

In part to try out AXDT, a flash plugin for Eclipse (which you can find here), I decided to create a simple experiment involving Inverse Kinematics. This is not a very useful implementation but the results are quite fun. Essentially, the angles of subsections of each kinematic chain are altered until they face the mouse. I quickly discovered this is not the best solution for IK, but just for fun I made a kind of windswept, fur or grass effect using about 200 IK chains.

As usual click the top screenshot to launch the experiment and click here for source:

New Source Code Page

2011-04-20T00:40:00.001-07:00

Hey guys,

Due to many requests being for source code I have added a source section to the blog. When my exams are over I'll work through adding source code to older projects but for now I've included a few from some new stuff I've been working on. Just click the tab at the top from anywhere to access it.

Happy flashing!

Sam

Update: Colourful Turtle

2011-04-19T09:35:00.000-07:00

In my last experiment I recreated a turtle vector drawing program, with a simple interface. I'll post a small update to that which adds some color to the output. Here are some screenshots, as usual click the first one to launch the image, and source code can be found at the bottom, enjoy and let me know if you make anything pretty!

Source:

package org.experimentalized
{
 import flash.display.Sprite;
 import flash.events.Event;
 import flash.events.KeyboardEvent;
 import flash.display.Graphics;
 import flash.text.TextField;
 import flash.text.TextFieldType;
 import flash.geom.Rectangle;
 import flash.utils.getTimer;

 [SWF(width='550',height='550',backgroundColor='#000000',frameRate='30')]

 public class Turtle extends Sprite
 {
  private var commandstring:String = new String("mv:30,lt:90,mv:10,rt:30");
  private var S:Sprite = new Sprite();
  private var Angle:Number = new Number(0);

  private var X:Number = 0;
  private var Y:Number = 0;

  private var R:int = 0;
  private var G:int = 0;
  private var B:int = 0;


  private var input:TextField = new TextField();

  
  private function newrun(e:KeyboardEvent):void
  {
    commandstring = input.text;
    S.graphics.clear();
    S.graphics.lineStyle(1,0xFFFFFF);
    S.graphics.moveTo(0,0);
    Angle = 0;
    X = 0;
    Y = 0;
  }

  public function Turtle():void
  {
   addEventListener(KeyboardEvent.KEY_DOWN, newrun);
  
   addChild(S);

   input.width = 530;
   input.height = 20;
                 input.x = 10;
                 input.y = 10;
                 input.background = true;
                 input.backgroundColor = 0xFFFFFF;
   input.type = TextFieldType.INPUT;
   
   input.text = commandstring;


   addChild(input);

   S.x = 275;
   S.y = 200;
      
   this.addEventListener(Event.ENTER_FRAME, handler);
  }
  
  private function handler(e:Event):void
  {
   R = int(128 * (1 + Math.cos(getTimer()/1000-0.8981)));
   G = int(128 * (1 + Math.sin(getTimer()/7473-0.3812)));
   B = int(128 * (1 + Math.sin(getTimer()/1273+0.1787)));
   
   var C:uint = (R<<16|G<<8|B);   
   
   S.graphics.lineStyle(1,C);
   var commands:Array = new Array();
   commandstring = commandstring.split(" ").join("");
   commands = commandstring.split(",");
   var i:int;

   for(i=0;i<commands.length;i++)
   {
    if(commands[i].charAt(0)=="m")
    {
     var dist:Number = Number(commands[i].split(" ").join("").split(":")[1]);
     X = X + dist*Math.cos(Angle);
     Y = Y + dist*Math.sin(Angle);
     S.graphics.lineTo(X,Y);
    }
    else if(commands[i].charAt(0)=="l")
    {
     var changeleft:Number = Number(commands[i].split(" ").join("").split(":")[1]);
     Angle -= Math.PI*changeleft/180;
     if(Angle<0) Angle += 2*Math.PI;
    }
    else if(commands[i].charAt(0)=="r")
    {
     var changeright:Number = Number(commands[i].split(" ").join("").split(":")[1]);
     Angle += Math.PI*changeright/180;
     if(Angle>Math.PI*2) Angle -= 2*Math.PI;
    }
   }
  

   //Resize to fit on the square after each iteration (purely aesthetic choice...)
   
   var Rect:Rectangle = S.getRect(S.parent);
   
   S.x += 275 - (Rect.x+Rect.width/2);
   S.y += 275 - (Rect.y+Rect.height/2);
   S.width = 550;
   S.height = 550;
  }
 }
}

Turtle: 30 minute experiment

2011-04-18T09:07:00.000-07:00

I had recently been reminiscing about IT lessons in year 3 where we were allowed to play around with those Turtle vector drawing programs. I thought I'd write one and share the results as a quick break from revision. Although it can't do much at the moment (the only commands are forward, left and right) with a bit more work I'm sure it could be made into quite an exciting program. You'll find the source code below and as usual just click the top image to launch the experiment.

Source code:

package org.experimentalized
{
 import flash.display.Sprite;
 import flash.events.Event;
 import flash.events.KeyboardEvent;
 import flash.display.BitmapData;
 import flash.display.Bitmap;
 import flash.display.Graphics;
 import flash.text.TextField;
 import flash.text.TextFieldType;

 [SWF(width='550',height='400',backgroundColor='#000000',frameRate='30')]

 public class Turtle extends Sprite
 {
  

  private var commandstring:String = new String("mv:30,lt:90,mv:10,rt:30");
  private var S:Sprite = new Sprite();
  private var Angle:Number = new Number(0);

  private var X:Number = 0;
  private var Y:Number = 0;

  private var input:TextField = new TextField();

  
  private function newrun(e:KeyboardEvent):void
  {
    commandstring = input.text;
    S.graphics.clear();
    S.graphics.lineStyle(1,0xFFFFFF);
    S.graphics.moveTo(0,0);
    Angle = 0;
    X = 0;
    Y = 0;
  }

  public function Turtle():void
  {
   addEventListener(KeyboardEvent.KEY_DOWN, newrun);
  
   addChild(S);

   input.width = 530;
   input.height = 20;
                 input.x = 10;
                 input.y = 10;
                 input.background = true;
                 input.backgroundColor = 0xFFFFFF;
   input.type = TextFieldType.INPUT;
   
   input.text = commandstring;


   addChild(input);

   S.x = 275;
   S.y = 200;
   
   S.graphics.lineStyle(1,0xFFFFFF); 
   
   this.addEventListener(Event.ENTER_FRAME, handler);
  }
  
  private function handler(e:Event):void
  {
   var commands:Array = new Array();
   commandstring = commandstring.split(" ").join("");
   commands = commandstring.split(",");
   var i:int;

   for(i=0;i<commands.length;i++)
   {
    if(commands[i].charAt(0)=="m")
    {
     var dist:Number = Number(commands[i].split(" ").join("").split(":")[1]);
     X = X + dist*Math.cos(Angle);
     Y = Y + dist*Math.sin(Angle);
     S.graphics.lineTo(X,Y);
    }
    else if(commands[i].charAt(0)=="l")
    {
     var changeleft:Number = Number(commands[i].split(" ").join("").split(":")[1]);
     Angle -= Math.PI*changeleft/180;
     if(Angle<0) Angle += 2*Math.PI;
    }
    else if(commands[i].charAt(0)=="r")
    {
     var changeright:Number = Number(commands[i].split(" ").join("").split(":")[1]);
     Angle += Math.PI*changeright/180;
     if(Angle>Math.PI*2) Angle -= 2*Math.PI;
    }
   } 
  }
 }
}

To make the output lines automatically fit the stage use the following instead:

package org.experimentalized
{
 import flash.display.Sprite;
 import flash.events.Event;
 import flash.events.KeyboardEvent;
 import flash.display.Graphics;
 import flash.text.TextField;
 import flash.text.TextFieldType;
 import flash.geom.Rectangle;

 [SWF(width='550',height='550',backgroundColor='#000000',frameRate='30')]

 public class Turtle extends Sprite
 {
  private var commandstring:String = new String("mv:30,lt:90,mv:10,rt:30");
  private var S:Sprite = new Sprite();
  private var Angle:Number = new Number(0);

  private var X:Number = 0;
  private var Y:Number = 0;

  private var input:TextField = new TextField();
  
  private function newrun(e:KeyboardEvent):void
  {
    commandstring = input.text;
    S.graphics.clear();
    S.graphics.lineStyle(1,0xFFFFFF);
    S.graphics.moveTo(0,0);
    Angle = 0;
    X = 0;
    Y = 0;
  }

  public function Turtle():void
  {
   addEventListener(KeyboardEvent.KEY_DOWN, newrun);
  
   addChild(S);

   input.width = 530;
   input.height = 20;
                 input.x = 10;
                 input.y = 10;
                 input.background = true;
                 input.backgroundColor = 0xFFFFFF;
   input.type = TextFieldType.INPUT;
   
   input.text = commandstring;


   addChild(input);

   S.x = 275;
   S.y = 200;
      
   this.addEventListener(Event.ENTER_FRAME, handler);
  }
  
  private function handler(e:Event):void
  {
   
   S.graphics.lineStyle(1,0xFFFFFF);
   var commands:Array = new Array();
   commandstring = commandstring.split(" ").join("");
   commands = commandstring.split(",");
   var i:int;

   for(i=0;i<commands.length;i++)
   {
    if(commands[i].charAt(0)=="m")
    {
     var dist:Number = Number(commands[i].split(" ").join("").split(":")[1]);
     X = X + dist*Math.cos(Angle);
     Y = Y + dist*Math.sin(Angle);
     S.graphics.lineTo(X,Y);
    }
    else if(commands[i].charAt(0)=="l")
    {
     var changeleft:Number = Number(commands[i].split(" ").join("").split(":")[1]);
     Angle -= Math.PI*changeleft/180;
     if(Angle<0) Angle += 2*Math.PI;
    }
    else if(commands[i].charAt(0)=="r")
    {
     var changeright:Number = Number(commands[i].split(" ").join("").split(":")[1]);
     Angle += Math.PI*changeright/180;
     if(Angle>Math.PI*2) Angle -= 2*Math.PI;
    }
   }
  

   //Resize to fit on the square after each iteration (purely aesthetic choice...)
   
   var Rect:Rectangle = S.getRect(S.parent);
   
   S.x += 275 - (Rect.x+Rect.width/2);
   S.y += 275 - (Rect.y+Rect.height/2);
   S.width = 550;
   S.height = 550;
  }
 }
}

Large Scale Stop Frame

2011-04-17T09:12:00.000-07:00

In my spare time I study physics at the University of Birmingham. We're currently having some building work done on our main courtyard, so with access to one of the security cameras from our main clock tower (provided by an unnamed physicist) I decided to document the events. I wrote a program which is currently running on the physics mainframe, which essentially grabs an image from the security camera every 2 minutes during the day. I compiled these images into a video (with about 6000 frames so far) and you'll find the initial results in the vid below:

I plan on taking a few more weeks of images, the above is about 6 weeks. Enjoy.

For those of you who are interested here is the bash source code:

#!/bin/bash
#PBS -j oe
#PBS -l walltime=240:00:00

CLOSING_TIME=1
WEEKEND=0

cd /home/st-01/pictures

while [ 1 ]
do
#Determine the current time
hour=$(echo `date +%k`)

#If the current time is between 9am and 6pm not inclusive
if [ $hour -gt 9 ] && [ $hour -lt 18 ]; then
#Still taking photos - don't close up yet
CLOSING_TIME=0

#Retrieve image from the server and save it with a unique timestamp
wget http://YOURSITE.com/IMAGE.jpg
timestamp=$(echo `date +%y-%m-%d__%H:%M:%S`)
mv IMAGE.jpg ${timestamp}.jpg
else
#Otherwise must be the end of the day during the week
if [ "$CLOSING_TIME" == "0" ]; then

#ZIP UP THE IMAGES FOR THE DAY
date=$(echo `date +%y-%m-%d`)
zip ${date}.zip `ls *.jpg`
#Remove all non-zipped images
rm *.jpg
CLOSING_TIME=1
fi
fi
sleep 120
done

Multi-Color-Space-Thresholding

2011-01-19T11:14:00.000-08:00

A few months ago I was commissioned to create some background subtraction technology in flash. The project fell through at the time. The final product wasn't as stable as I'd hoped it might be. I thought that since the project fell through I would share some of my findings to see if the collective flash community might have any ideas or suggestions as to how one might implement this kind of technology.

The idea of background subtraction is to separate two parts of an image, the foreground and a "static" background. Here is an example. Given the two images on the left, how does one extract the image on the right. You might think this is fairly easy, just look at the difference in color between the two you might say. Unfortunately it isn't as simple as this.

Firstly illumination and varying camera brightness cause a problem, not only does the foreground constantly change color, but also the background. Most web cams automatically adjust to a white point. You'll notice this if you hold a white sheet of paper against the web-cam, the background will dim. This means that in measuring the difference in RGB color for each pixel it is likely that the whole screen will be completely different from one frame to the next, not ideal if you want to separate out smaller regions!

The method I chose to incorporate was to use multiple color spaces, combined in order to create a new color space which was optimum for this kind of a background subtraction scenario. Here is the program I used to determine the optimum subtraction for each color space. Just click on the image to launch it:

Initially a background is captured, the user steps out of the frame, and a still bitmap image is taken, then for each color space a comparison is made. If the difference between given pixels is greater than a threshold for any color component (or a combination of the three) then the pixel is deemed to be in the foreground. The three color spaces used in this case where YUV, normalized RGB and normalized YUV. The latter of these I haven't seen in use before, but it gives reasonable results.

Once the image has been thresholded an alpha mask is applied to the current web-cam frame, and this image is used as the foreground. This allows some very impressive things to be done. The background can be replaced by an image, or another video (apple make use of this in their software Photo Booth), but more excitingly we now have two image planes, which means 3D!

Here is an example of background replacement:

In the image below you'll see 3D in action (excuse the poor lighting conditions), click to launch it but remember, it probably won't work fantastically. Just click to launch it:

The 3D angle can be controlled by head position (motion tracking) allowing you to look around the person in front of the camera which is quite an interesting effect.

The main issues with the project were that lighting conditions are constantly changing, and can vary hugely from web-cam to web-cam. There are other more computationally intensive approaches which flash may just about be able to handle, but unfortunately my brain cannot. Enjoy the experiment, and let me know how it works with your web-cams!

HTML5 Mandelbrot Explorer

2011-01-19T09:06:00.000-08:00

A simple Mandelbrot explorer for HTML5, in javascript. I plan on optimizing and extending the functionality of the example when I have a bit less uni work to keep up with.

First Canvas Experiment: BitmapData

2011-01-18T03:45:00.000-08:00

Lots of people have been talking about html 5 and canvas for a while now. As an actionscript purist I had decided not to venture into the world of incompatibility quite yet, but having seen some of the cool chrome experiments again recently, I decided to give writing some canvas toys a little go.

My first experiment is a simple one, just some randomly updating pixels on a screen.

Here is the .js code:

function setPixel(bitmapData, x, y, r, g, b, a) {
index = (x + y * bitmapData.width) * 4;
bitmapData.data[index+0] = r;
bitmapData.data[index+1] = g;
bitmapData.data[index+2] = b;
bitmapData.data[index+3] = a;
}

element = document.getElementById("bitmap");
canvas = element.getContext("2d");
width = parseInt(element.getAttribute("width"));
height = parseInt(element.getAttribute("height"));

setInterval('update()',30);

function update()
{
bitmap = canvas.createImageData(width,height);
for (i = 0; i < 10000; i++) {
     x = parseInt(Math.random() * width);
     y = parseInt(Math.random() * height);
     r = parseInt(Math.random() * 256);
     g = parseInt(Math.random() * 256);
     b = parseInt(Math.random() * 256);
     setPixel(bitmap, x, y, r, g, b, 0xff);
 }
 canvas.putImageData(bitmap, 0, 0);
}

Transparency and Reflection

2011-01-15T14:07:00.000-08:00

I haven't posted anything new on my blog in quite a while. Most of my time has been spent working on writing a fully function Actionscript plugin for Gedit, which will (with any luck) improve the development experience for users of Linux.

Anyway I thought I'd post some eye candy, just a simple transition between two ASTrace renders. I be plan on working on a pixel bender filter to carry out these effects in real time. A kind of one-track raytracer which optimizes a single scene with a central sphere. This should be possible with two displacement filters, one for reflection and one for refraction. For now, here is a prototype without full 3D rotation (Click to launch then move the mouse left or right to change reflectivity):

Actionscript Debugging Working in GEDIT (Sort of...)

2010-12-04T16:11:00.000-08:00

In my previous post I described how to write a shell script for Gedit under linux that would compile an actionscript/mxml project. I have come up with a reasonably good method for outputting trace statements to the Gedit console. Here is the script that I use to do it:

#!/bin/sh

EHOME=`echo $HOME | sed "s/#/\#/"`
DIR=$GEDIT_CURRENT_DOCUMENT_DIR
FILE=$GEDIT_CURRENT_DOCUMENT_NAME
EXT='swf'

echo "Compiling: " $GEDIT_CURRENT_DOCUMENT_PATH
echo '--------------------'

SWF=${FILE%as}${EXT}

cd ${DIR%${FILE}} > /dev/stderr

export PATH=/home/experimentalized/developer/sdks/flex_sdk/bin:$PATH
mxmlc -debug=true -static-link-runtime-shared-libraries=true ${FILE}
gnome-open ${SWF}

echo "Waiting for Flash Player to connect"
sleep 4

OUTPUTDIR=/home/experimentalized/.macromedia/Flash_Player/Logs/flashlog.txt

TOTALLINES=`sed -n '$=' ${OUTPUTDIR}`
LINE=1
CURRENT=`sed -n "${LINE}{p;q}" ${OUTPUTDIR}`

while [ "true" ]
do
if ps ax | grep -v grep | grep flashplayerdebugger > /dev/null
then
TOTALLINES=`sed -n '$=' ${OUTPUTDIR}`
if [ "$TOTALLINES" -ge "$LINE" ]; then
   CURRENT=`sed -n "${LINE}{p;q}" ${OUTPUTDIR}`
   LINE=$(( $LINE + 1 ))
   echo ${CURRENT}
fi
else
break
fi
done

exit 0

The script initially does the same as the one in the previous post, but sets -debug to true. When the flash debug player runs it outputs data to a log file. This file is called flashlog.txt and is stored in ~/.macromedia/Flash_Player/Logs/ by default on linux. The script runs through lines in the trace output and echos them to the console one at a time. When it notices that the flash player is closed, it exits and when it reaches the last available line it stops tracing. It does in fact work (although there is a bit of latency as debugger writes to file -> is read by script isn't instantaneous). It may not be great for things like ENTER_FRAME events, and current mouse position, but it is enough for me. Just install it in the same way as I did in the previous post and set a key-shortcut like control-alt-d for debugging.

I think I'm finally happy with my flash setup on Linux which is great (although code completion isn't there so I may take a look into that). Here are some screenshots:

Compiling Flash from GEDIT

2010-12-04T06:05:00.000-08:00

In the previous post I discussed an option for developing flash on Linux, using the free flex sdk, and free software. The main problem I found was that every time I wanted to compile and run a file, I had to type some commands in the terminal. I'm pretty lazy when it comes to programming and I'm sure most of you agree that it helps to get everything working as fast as possible.

To solve the issue I wrote a simple shell script which compiles and runs .as files, just like adobe flash does. This tutorial is for Linux users, if you're using windows I'd suggest using something like flashDevelop, which should do all of this for you anyway, if you're using Mac OS and can run Gedit from the terminal, it is an option but probable isn't ideal.

So first off, if you haven't got it yet install Gedit and follow my previous tutorial at:

http://experimentalized.blogspot.com/2010/11/developing-flash-on-linux.html.

Once everything is set up head into Gedit and go to Menu > Edit > Preferences > Plugins and enable the "External Tools" plugin. If you don't have it you'll have to install it.

Exit Preferences and go to Menu > Tools > Manage External Tools...

Click the icon with a green +, to create your own 'tool'. The idea is that when you run the tool, a shell script runs mxmlc on your currently open document, and then opens the generated swf in the flash debug player.

In your new tool copy and paste the following

#!/bin/sh

EHOME=`echo $HOME | sed "s/#/\#/"`
DIR=$GEDIT_CURRENT_DOCUMENT_DIR
FILE=$GEDIT_CURRENT_DOCUMENT_NAME
EXT='swf'

echo "Compiling: " $GEDIT_CURRENT_DOCUMENT_PATH
echo '--------------------'

SWF=${FILE%as}${EXT}

cd ${DIR%${FILE}} > /dev/stderr

export PATH=PATH_TO_FLEX_SDK/bin:$PATH
mxmlc ${FILE}
gnome-open ${SWF}

replacing PATH_TO_FLEX_SDK with the complete path to your flex sdk (which you may have set up in the previous tutorial). If you haven't installed gnome-open use sudo apt-get install gnome-open in a terminal window.

You can set up a shortcut key to run the script. Then go back to your project class and run the command! If everything has worked you should see a window with your newly compiled swf running inside it!

There are a few problems with the script currently. Firstly the mxmlc compiler compiles to your src directory (wherever the actionscript file is). Second, there is still no debugging, which is a real shame. Gedit allows stdout to be displayed in the editor, so I am thinking of a way of displaying trace arguments right in Gedit. This would be an ideal solution to free and simple flash editing.

Here are some images showing Gedit compiling flash:

Developing Flash on Linux

2010-11-22T06:50:00.000-08:00

I recently bought a new net-book, and having no patience whatsoever with Windows 7 Starter, I decided to install Ubuntu. The OS works fantastically with only 1Gb of RAM and as a first time Linux user I was really impressed with the ease of use and customisability of Ubuntu. Clearly as a flash developer I needed a way to develop flash, to at least a basic level (I wasn't after full debugging or any fancy features, just a way to compile some apps and to allow me to work on the train or in front of the TV)!

I decided to keep it simple; just a text editor with command-line compiling and testing.

So here is how I did it:

1. Install the flex sdk:

The free SDK is downloadable from adobe ( http://opensource.adobe.com/wiki/display/flexsdk/Download+Flex+4 ), I downloaded 4.5 to try out some of the new features, but you can choose the build that meets your requirements. Save the library somewhere to your local disk (I chose /home/USER/developer/sdks/flex_sdk). The next step is to enable the terminal to access the executables in the flex_sdk which will build your programs.

Open a new terminal and type sudo nano ~/.bashrc (you may be asked to enter your password) and add the line:

export PATH=/home/USER/developer/sdks/flex_sdk/bin:$PATH

to your bashrc file. To test it has worked restart the terminal type "which mxmlc", it should echo the path you just provided.

2. Download the Flash 10.1 Debugger for Linux:

Download the Debugger and install it using:

$ cd /tmp

$ wget http://fpdownload.macromedia.com/get/flashplayer/current/install_flash_player_10_linux.tar.gz

$ tar -zxvf install_flash_player_10_linux.tar.gz

$ cd install_flash_player_10_linux

$ ./flashplayer-installer

in your terminal.

Hopefully you'll have a functioning debugger now. Check it works by finding an swf, setting all swfs to open with the flash player, and run gnome-open file.swf, and the debugger should open in the flash player.

Failing this just use the flash for Firefox plugin.

3. Install AS3 and MXML language files for Gedit:

If you don't have Gedit, get it, its a great little text editor, and for me at least it does everything I need to (at least for editing AS3 files). Download the MXML and AS3 files from http://conic.se/blog/posts/8/ and copy them into ~/.local/share/gtksourceview-2.0/language-specs/. When you run Gedit you should be able to switch to the correct syntax highlighting for each language.

Finally put all three together. Create a directory containing the actionscript library you want to compile, and in your command line run mxmlc test.as. If you've followed the steps you should have created an swf. Finally run the swf using gnome-open test.swf.

Here are a few screenshots of the system in action:

Good luck developing AS3 in Linux

Some Beautiful Transparency Renders in ASTrace

2010-11-01T03:28:00.000-07:00

My raytracing project has been on hold for a while as I have been fixing minor bugs and not really creating anything new. I am rewriting some features of the raytracer completely from scratch which will hopefully improve performance and clarity of the code. I will implement features such as bounding spheres for intersection tests, as well as possible octrees or similar to improve performance for large numbers of objects. Once the engine is working fully in flash I will port it to alchemy, and hopefully with those performance boosts the engine will be ready for distribution.

Here are a few renders showing transparency and reflection that I created last night. Both are the same scene with different sky boxes applied. You can download the full size images (2200 by 1600px) by right clicking and saving as:

Soft Shadows in ASTrace

2010-10-28T13:00:00.000-07:00

Here is a nice example of fully antialiased soft shadows. The source light uses about 20 seed points spread out using a pseudo-random function, to produce reasonable effects.

Improved Supersampling and Antialiasing

2010-10-27T15:34:00.000-07:00

I decided to improve the supersampling/antialiasing methods in my raytracer. Previously I applied a blur filter to the image after upsizing and then returned the image to its original size. This is not a very realistic or accurate antialiasing method so I decided to add some real supersampling to the raytracer. The two images below both have the same resolution, but the image on the right appears more realistic with fewer jagged edges. This is achieved by firing multiple rays for each pixel, and based on their relative position, calculate their contribution to the colour of that pixel. The obvious downside to this method is a largely increased rendering time, proportional to the number of rays per pixel. This means that 16 rays per pixel takes 16 times longer than a single ray. Quality definitely comes at a computational price. I think randomising the rays may improve the antialiased image quality, instead of firing them across a uniform grid and I will look into that.

The next updates are likely to be cloud maps and a sun object (infinite directional lighting).

Perlin Texturing in ASTrace

2010-10-25T15:05:00.000-07:00

I've added simplex noise volumetric texturing to ASTrace. I found this nice little Simplex noise class by Sjeiti and implemented it in the library. Simplex is slightly faster than Perlin noise in 3 and 4 dimensions so it is ideal to use as a volumetric texture for primitives in the tracer, here are a few examples:

As an extension I decided to create an animation using 4-dimensional simplex noise, just click on the image to launch it. I am planning on implementing a cloud sphere, and this would be ideal for animations of clouds:

Material Properties

2010-10-21T07:38:00.000-07:00

Choosing the right material to represent a particular object is important when producing realistic 3D graphics. Factors like refractive index, specularity, and reflectivity all affect how we perceive an object both in the real world and on screen, so ideally the real world case should be simulated as closely as possible in its computer based counterpart. The three images below show how differing physical features completely change the appearance of a scene. In the top image the sphere is 100% reflective, in the second it is partly transmissive and partly reflective and in the last image, the sphere is fully transmissive with a refractive index of around 1.08. I am pleased with the results I am getting from the raytracer, but adding more features increases the render time dramatically, especially for large numbers of objects. I am looking into porting the library to C++ for use in alchemy, which would show a dramatic increase in speed, possibly rendering scenes like the one below in real time. Till then here is the library.

ASTrace Pre Release

2010-10-21T02:08:00.000-07:00

Although the library is nowhere near complete, I thought I would release a beta to see what you think. At this stage feedback would be really useful, including any suggestions you might have about extensions to the project. I should note that there is no documentation as of yet, this will be coming as soon as I manage to get asdoc to run properly. There should be plenty of scope for you to play around with the library, it'd be great if you could send me some of your renders.

Here is a link to the library: ASTRACE

and here are some of my favourite renders using the library:

Some more ray tracer features

2010-10-11T08:50:00.000-07:00

Here are a few more demos of new raytracer features:

Water (with transparency and reflection):

Environment and Texture Mapping:

Fog - Linear, Square and Exponential decay

Visible Lights (ideal for rendering sunlight, lamps etc):

Soft Lighting (one soft light with 10 seeds - therefore only noticable on some shadows):

Triangular Faces:

Transparency (with refraction, internal reflection etc):

A few more features are on their way (including UV mapping, environment mapping, and Fresnel shaders) and once those features are finished I will release the library.

Reflective Recursion

2010-09-23T11:31:00.000-07:00

With the exception of refraction, which I am not yet happy with (total internal reflection problems), the raytracer is coming together fantastically. This is my favourite render so far featuring diffuse and specular reflections with 2 pass antialiasing. The image was rendered at 2200x1600 and cropped to give the final image:

Not bad for flash, about 30 minutes render time.

Once mathematical problems with internal reflection are fixed I will be releasing the library under an open source license, let me know if you have any last minute requests!

Below is a similar image but rendered to 3300x2400 pixels in about 90 minutes:

New Ray Tracer Features

2010-09-20T08:00:00.000-07:00

I mentioned a short while ago that I was creating a brand new ray tracer for actionscript 3. It is beginning to take shape and I thought I'd run through a quick feature list:

Objects: spheres, planes, boxes - triangular meshes in the pipeline
Materials - reflective, transparent, bitmap
Unlimited reflection and refraction (within reason)
Direction lighting (multiple light points)
Phong shading
Camera with 6 degrees of freedom
Sky object - simple sky rendering
Save output as .JPG, .PNG or .BMP
Render progress
Color lights
Soft lighting
Low resolution real-time rendering (for small numbers of objects/lights)
Antialiasing and effects
Anaglyph rendering

No doubt the feature list will grow and let me know if you have any requests. I would really like to have curved surface and formula collisions as part of the package, so I'll try to get this working then release the library under the name ASTrace. Currently the first below (10 spheres, 1100x800 resolution, 1 light) renders in about 10 seconds which I am very happy with, and the second scene (30 spheres, 1100x800, 1 light, 10 reflections) in about 150 seconds - not so good, but not bad.

I will post demos up as I make them, here is one showing reflection and planes. It looks like there is something wrong with the reflections despite the render looking fantastic, so I will look into that (100 seconds, 1100x800):

Another nice demo, still haven't fixed the reflection problem though:

A new example with the reflection problem ironed out (50 spheres, 2200x1600, about 15 minutes):

An example showing antialiasing and plane/sphere reflection:

Underwater Scene

2010-09-12T09:36:00.000-07:00

Just created quite a nice little underwater scene, with bubbles and lighting. Just need to add some fish! I've been finding it quite relaxing just to watch. It is completely dynamically resizable just like the cloud background I made a few months ago. Click to launch it.

Conway's Game Of Life using Pixelbender

2010-09-11T15:07:00.000-07:00

Couldn't resist trying to create a pixelbender filter for use in the Game of Life. In an article a few years ago I created a simple Life application. Pixelbender has the potential to massively increase the speed of calculations such as those used in Life, the results are obvious. On top of this the simplicity within flash is fantastic, to advance the game you simply need to apply a filter to a bitmapData object. Click to launch the app:

Experimentalized - New Look

2010-09-11T10:27:00.001-07:00

Just updated my homepage, check it out here.

Real Time Regional Differencing

2010-09-11T03:56:00.001-07:00

I little while ago I produced a method for extracting interesting regions from images which I called regional differencing (see post). I have optimised the code, and it now runs in real time. It works very well as a simple edge detector with the ability to produce much thinner lines than the Sobel detector, notice in the image below the maximum line thickness is one pixel. The algorithm works by comparing more and less pixelated versions of an image to find local differences compared to a local mean.

To improve the algorithm I switched from the RGB colour space to NUV as this improved results (albeit reducing performance marginally). The detector doesn't quite have the quality of something like the Canny detector, but it requires a lot less processing which in flash is very important!

Anyway check out the demo by clicking on the link below, the slider changes the pixel size of the comparison bitmap, with some interesting results. The default settings use a size of 2 pixels producing lines of a maximum one pixel thick.

Visual Human Interfaces

2010-09-10T07:05:00.000-07:00

Making human interfaces intuitive, simple and accurate is a huge challenge. Some of the biggest challenges lie in the field of motion and gesture detection. Analysing visual data in real time can be very processor intensive.

This is a fairly simple implementation of an interface which has the ability to track on screen button presses and swipes (it is part of an ongoing research project):

Click to launch a demo video:

Crossfade Using Pixelbender

2010-09-06T05:07:00.001-07:00

I am currently doing some work for a client which involves background subtraction. I have been getting into using pixel bender to calculate filters in flash for a while now, but doing some research I found there is actually huge scope for using pixel bender to carry out other calculations (see this article).

The following example uses pixel bender as a part of the background subtraction process. Consecutive frames from the webcam are blended with all previous frames. The eventual result is to produce a good estimate of the background pixels. The example uses the blendShader property of a display object with blend mode set to BlendMode.SHADER, and a custom Pixelbender shader that mixes pixels. Check it out (click to launch):

Ray Tracing Library AS3

2010-08-31T08:32:00.000-07:00

About a year ago I wrote a ray tracer. I've decided to the same thing again, building from the ground up, and taking a completely OOP approach - which I didn't do before. I was very pleased with previous results, but given the lack of structure implementing certain features became a real headache, and a lot of code had to be rewritten each time I wanted to make a small change.

At the same time I will try to speed up the engine, try to stick to bitwise operators and vectors whenever possible. With any luck it'll be up and running in the next few weeks, but I will keep you updated along the way.

Here are some screenshots from the previous ray tracer:

FlashMath Demo 1

2010-08-09T03:29:00.000-07:00

Just a really simple demo, which uses the FlashMath library. Click to launch it. The demo uses a string evaluation function to generate the curve. This function is also used to calculate the integral of the curve using Simpsons rule between min and max, and by clicking on the graph, finite differencing is used to calculate the gradient of the curve. Data set and graph classes are used to store / draw the data. The parser was created by http://www.undefined.ch/ and is a really useful tool! The demo might be a bit buggy at the moment, but its a good sign of things to come!

Experimentalized Maths Library

2010-08-03T14:26:00.000-07:00

It struck me today, that although I reuse a lot of code and classes, the one thing I tend to rewrite each and every time I start a new program is the mathematics. I dread to think how many hours this has wasted me over the years, so I finally decided to write a toolkit encompassing almost anything maths based. So far I've written a couple of constant utilities, one for mathematical constants, and one for scientific constants and a complex number class. Currently on the list are:

Matrices
Data sampling and statistics
Quadrature (integration) - Rectangle, Trapezium & Simpson's rule ✔
Numerical differentiation - finite differencing ✔, runge-kutta (and other ODE solvers)
Graphs
Vectors ( 2, 3 ✔ and N dimensional)
Geometry class & trigonometry solvers
Probability
Random numbers (Mersenne Twister, other PRNGs)
Time and date
Complex numbers ✔
Bitwise operators ✔
Mathematical constants ✔
Scientific constants ✔

It would be great if you could let me know what kinds of maths utilities you would find useful, and even better if you have some of your own code and would like to collaborate with me on this.

Update: Your suggestions:

Bezier curves (Cubic & Quadratic), Bezier surfaces?

FLAR Toolkit - First Go

2010-08-03T06:58:00.000-07:00

I thought I'd finally get round to having a go with the FLAR toolkit (an augmented reality toolkit for flash). I made a marker which will be used in any AR experiments I do on the site, then quickly made a test program. All I can say is it works quite nicely and I'll be playing around with it in the near future. Click the second image to run the test!

Webcam Gestures in Flash

2010-08-01T15:10:00.000-07:00

I'm currently creating a game which involves gesturing as the primary control method. For those who aren't familiar with the term gesturing, it was created to describe a set of motions carried out on a touch screen. I thought it would be pretty cool to make the keyboard and mouse completely obsolete and applied my gesturing algorithm to the webcam. Getting timings right with the webcam was the hardest part. You can choose when to start and stop using a mouse, but how do you tell when one gesture ends and the next begins on the webcam.

Click below to watch a video of the experiment in action:

It works by calculating the angles travelled in a gesture. It compares these to a list of angles which relates to a certain gesture. For example for a straight line in the positive horizontal direction this would be 0-0-0-0-0 or in the negative horizontal 180-180-180-180. The program determines which preset gesture the carried out gesture is most like and then performs an action based on this choice. The result is by no means stable, but using a better set of thresholds and presets can improve the performance dramatically.

Click here to launch the experiment and have a go yourself. Remember you'll need a webcam to do so.

Computational Textual Analysis: Is it literature?

2010-07-27T09:44:00.000-07:00

Is there a definitive definition for literature? I was thinking to myself about this the other day, and decided to find out. Before I set out on this experiment I'll make it clear that I think the answer is very subjective, and that although there are aspects found within most books that are considered true literature, these are not found within all of them. The initial list of books that I considered literature (with which to train my software) are widely spread in terms of theme, publication date and writing style, but the key point is they are chosen, therefore a concept of literature already exists in the person who chooses a list. The program I set out to write would be able to determine whether or not any piece of text was (or wasn't) literature by matching the similarity of various features of a piece of text, to this concept of true literature. It should also be noted that the program is language independent.

I'll start by explaining briefly some of the characteristics that I decided to use in order to measure the level of literature in a piece of text:

Sentence length
Average word length
Unique words
Vocabulary Score (unique words / total words)
Vocabulary Deviation
Character Deviation
Word Entropy
Character Entropy

Sentence length and word length were calculated by splitting the text into components with the splitting parameter for sentences being a full stop, and for words being a space. Note that words can therefore include punctuation; "this" classes as a different word to "this." when it is at the end of a sentence. This gives us some information about where words are used in sentences.

Unique words are simply words without repeats, for example in the text chunk "hi hi there there there", the unique words are "hi" and "there". These can be used to provide what I've called a vocabulary score. The vocabulary score essentially allows us to create a measure of the range of words used, that is (almost) independent of the length of the text. I say almost, because the range of vocabulary in the English language is limited, therefore as text chunks become longer (for example in a very long novel such as War and Peace) the vocabulary score will automatically decrease.

The vocabulary and character deviation involve counting the number of repeats of each word and character - then calculating the standard deviation of this data set. The former is a good measure of how comfortable an author is using a wide range of words, as opposed to using them occasionally.

Finally two very important measures of "literaryness" are the entropy of words and characters. During initial experiments I found that these tend to stay fairly constant for the "literature" used for training. To calculate the entropy of a set the following calculation is used:

Entropy = - SUM [ Ki log2 ( Ki ) ],

where Ki is the probability of a member of the set (in this case a word or character) occurring.

The next step of the experiment was to find a transform of the values of the above features that yielded very similar results for all of my training set.

The following set of books were used in the training set:

Franz Kafka, Metamorphosis
Oscar Wilde, The Picture of Dorian Gray
Sir Arthur Conan Doyle, The Hound of the Baskervilles
Joseph Conrad, Heart of Darkness
Jules Verne, Around the World in 80 Days
J.D. Salinger, Catcher in the Rye
Anthony Burgess, A Clockwork Orange
Bram Stoker, Dracula
George Orwell, Down and Out in Paris and London

And a value, which we'll call L was determined to be the smallest deviating transform of the textual features where:

L = (Word entropy + Character entropy - Word length) / Vocabulary score

Other features were found to range too much between the works.

Given an average L value the distance away from the mean was used to give any test text a literature score. Unfortunately this blog did not receive the title of literature, but then nor did Harry Potter and the Philosophers Stone, or Twilight, or a Mills and Boon title, A Fool For Love, so it seems to work quite nicely.

A book I would consider to be literature, not on the training set was Kidnapped by Robert Louis Stevenson, and it did indeed score highly on the literature front which means the system works!

Below is the application, just click to launch it and post a comment with any results you might find:

Currently the results are a bit spurious, mostly because thresholds are fiddly to get right, but with a bit of work and some other parameters I have been thinking about, this kind of textual analysis really might help us spot the next classics! The program currently works best with whole books, there are a load of free eBooks that are now in the public domain which you can test the software with!

2D Dynamic Shadow Casting (and Lighting)

2010-07-21T04:58:00.000-07:00

After having a little think about how to do this effectively, the answer was actually rather simple (which ins't entirely in keeping with the rest of this blog). My previous attempts involved raytracing the 2D scene. By stepping through every single point in the scene, and calculating the path to it from the light source a per pixel map of brightness can be generated. I decided however that this was far to CPU intensive for high complexity scenes so went down a simpler route. The basic algorithm was:

Trace a path from the light source to each vertex in each shape,
Continue these paths outwards from the shape, thus casting a shadow
Generate polygons to be filled in the shadow colour with pairs of these paths
Draw a light mask (just a circle with a transparency gradient over the floor)

Just click the first image to launch the experiment. I am quite pleased with the results!

The image below shows the intermediary path tracing step:

By changing the light source mask a directional torch like effect is simple to reproduce, again just click to launch the app:

Colour Palette Creator

2010-07-18T11:54:00.000-07:00

I am sure that there are hundreds of tools like this on the web, but I thought it would be quite interesting to produce a colour palette based on an image. Imaging you are designing a website and you really like the colours used in a particular piece of art, then you've come to the right place. This software will extract the most common colours in an image, and also give you the average colour.

The method used to calculate these is very simple. To calculate the average colour, simply sum all the RGB components of each pixel and divide by the total number of pixels. I do this using bitwise operators where:

R = HEX >> 16 & 0xFF
G = HEX >> 8 & 0xFF
B = HEX & 0xFF

and HEX = (R<<16 | G<<8 | B), useful stuff!

To calculate the palette I create an accumulator array which counts the number of each colour in the image. Before using this I reduce the number of colours in the image using some simple math.

I hope you find it quite interesting to have a play around with, just click the image to launch it. You can load your own images from your local computer to play around with it.

Real Time Feature Point Tracking in AS3

2010-07-17T16:36:00.000-07:00

Its a bit late, so instead of posting a long informative post about how feature point tracking works I thought I'd just upload some of my results from this evening. I think its quite exciting stuff. The image shows feature point tracking working relatively well on my pupils, and also on other facial features (the last two images). I am very pleased with the result.

A related project I have also been working on this evening is optical flow which I am close to getting

working, here is a preview of what is to come:

Both methods are used in tracking objects in moving images and have been implemented in real time. I will post sample movies and some explanations shortly so you can play around with them yourself.

Computer Vision: Regional Differencing

2010-07-13T13:38:00.000-07:00

I have always been very excited by the idea of computer vision. At the same time I find the concept of teaching a computer to sift through a grid of pixels, whilst gaining some sort of an insight into their meaning quite astounding. When we as humans look at a scene we can immediately identify objects of interest to us. We look at a boat and immediately can tell that it is a boat and not for example a chair. We can do this, even if we have never seen that particular boat before. Computers struggle with this kind of visual finesse, although there are examples (see Assimo) that are already performing very well.

Back to the point: I was looking at this situation and thought to myself that humans find it incredibly easy to establish important features in any image. Take for example the image to the left, we can see clearly the line where the water meets land at the far edge of the lake, we can see trees, we can see a ridge and its reflection, and we can see clouds. These geometries are made visible to use because of contrast and colour differences between regions in the image. I decided to think of a way for a computer to do this. I'm sure the method has been done before under a different name, but I couldn't find any material on it so I've decided to call the method "Regional Differencing".

The method is fairly simple, but I am happy with the results. First the image is split into square regions of a constant size. The colour of these regions is equal to the average colour of the pixels contained within it. The result of this is a kind of pixilation as can be seen in the picture to the right. Now taking the colour values of every single pixel in the previous image, we can compare the value to that of the average regional colour.

The result of this is quite interesting because areas that don't fit in with their surroundings are clearly distinguishable in the image. In this article I'd like to argue that this is part of the reason why humans are so good at picking out the geometries mentioned above. Humans can happily distinguish between different regions, even where differences are relatively subtle. Combining this ability with memory of collections of shapes, we can identify objects very successfully.

So lets take a look at some of the results (as always click the first one to launch the application and try it out yourself):

The above 3 images show three different threshold levels for a constant pixel size, but if you run the app yourself you can also vary the pixel size yielding interesting results. At high thresholds it is interesting that the first objects that are made out are the trees and the line at the end of the lake, whereas the last objects made out are the clouds. Looking back I wonder if I found myself looking at these points before anything else.

There are many other ways to produced these kinds of data, including the Sobel operator method shown in various previous posts but sometimes it is nice to take a new approach.

Regional Growth Segmentation: Superpixels

2010-07-12T08:05:00.000-07:00

I recently came across some impressive software from some researchers at Stanford University (who else), called Make3D which takes any 2 dimensional images - preferably outdoor images, and converts them into 3D models. The whole 2D to 3D process begins with a method called image segmentation, where structures in an image are separated into superpixels. Superpixels are collections of pixels with similar properties - for example saturation, colour, brightness etc.

I decided to write some software capable of creating the superpixel structure, and segmenting an image. The route I went down is called regional growth segmentation. Superpixels grow outwards from a sample pixel, and depending on the similarity of tested pixels to the superpixels, they are either added to the superpixel, or create new superpixels...

Here are a few results with different thresholds for similarity (again, just click the first image to launch the application).

I'll take a look at some of the Make3D source code to see if I can generate some 3D planes from my superpixel, so stay tuned!

Generating Normal Maps: 2D Images

2010-07-11T09:58:00.000-07:00

The normal map used in the previous post was generated from a 3D model, so calculating normals was quite trivial. Taking any two dimensional image and calculating accurate realistic normals on the other hand is not. I have used a simple method using Sobel operators which seems to work quite well.

The Sobel operator provides X or Y gradient information about a certain image. Lets take a look at an example (Picture courtesy of my lovely girlfriend Camilla). The picture below shows a 2D image, with no 3D data whatsoever.

The sobel operator works by calculating the gradient of an image based on a range of pixels surrounding the pixel being tested.

First the image must be turned into a greyscale image, so that only brightness values are taken into account. Then a sobal operator is applied in the vertical and horizontal direction.

The results of applying the sobel operators can be seen in these two images. With the horizontal and vertical sobel operators respectively. These images correspond to the red and green channels in the final image. Since we have no sensible way of calculating a bump map for the two dimensional image the blue channel will just be set to a maximum throughout the image.

Finally we can apply this to the 2D Deferred Normal Lighting simulation I wrote about in the last post. The effects are quite impressive, creating a distinctly 3D look from a 2D image (Just click the image to launch the application):

To expand on this slightly further I thought it would be interesting to apply this to a webcam stream. This meant calculating a normal map every frame on top of the per pixel lighting so the resulting application is quite CPU intensive. I'm not quite as pleased with the effects as previously as there seems to be a lot of noise in the image. It might work better for you guys, just click the next image to launch it:

2D Deferred Normal Lighting

2010-07-11T07:41:00.000-07:00

Continuing on the same lines as my previous post I thought I would create a few more 2 dimensional lighting simulations. With a little help from a post on normal mapping from a post on Planet Pixel Emporium I was able to create some real time 2D deferred normal lighting using actionscript. The simulation works on a per pixel basis so for large images the method would get very slow.

First lets take a look at the final result and then I will explain how it works. Click the image to the left to start up the application. You'll notice that moving your mouse around over the image moves the light source. Not only does this change information about how far the light should spread, but also the direction of the light with respect to every pixel on the screen.

This allows images to be rendered with a far more realistic depth and 3D feel (compare it to the original image on the right). For this reason the method is used in many modern computer games.

The effect is created using a normal map. A normal map is a way of encoding data about the orientation of a plane using RGB colour. The red channel in the image represents the horizontal gradient of a face, the blue channel represents the vertical gradient, and the blue channel represents the height data (a bump map). The image below shows the normal map used for the image. I created the application by calculating the dot product of the normal at each point in the image with the light vector shining onto that pixel from the mouse's location.

The greater the dot product the more direct the light shining onto a point. In addition to this a distance falloff is used for the light to create the torch-like effect. I just use a factor of one over the square root of the distance as my falloff.

Obviously what isn't being considered in this is shadow casting so it isn't quite a real ray trace, but using bump map information it would be possible to create a real time semi 2-d ray trace.

Just for fun here is another sample, just click to launch it:

2D Dynamic Lighting - well almost

2010-07-09T04:04:00.000-07:00

I had a nice idea to create a 2D dynamic lighting experiment, where various light sources could be moved round and cast shadows in real time. I got started on the experiment and created a class to hold a coloured light source and then I got a little too excited by some of the pretty generative artwork I was making and decided to change the purpose of the experiment. I'll briefly explain how the light sources work. A light source is made up of a point, a colour and a falloff rate. By measuring the distance from each light source in an image, and summing the light values at those points it is simple to calculate the light intensity at each point in the image. Here are some results (just click to run the app):

Some of the effects remind me of binary star systems. Here are 2 more apps showing real time moving light sources with various effects:

Circle Packing - brute force approach

2010-07-07T10:04:00.000-07:00

Earlier this year, as part of my degree, I carried out a project that involved measuring the fractal dimension, and packing densities of various systems. I thought I'd have a play around with something along similar lines, circle packing.

There are many subtle and interesting and above all intelligent ways of packing circles into spaces, but this is not one of them. I decided to take a brute force approach. This is the structure my algorithm took:

Pick a random point, if it is within any circles that already exist find a new point
Increase the radius of that point until it overlaps with either the edge of the scene, or another circle on the scene.
Draw the circle

This is as far as I can tell, both the simplest approach and the slowest. Lets take a look at the results, click the image to run the application. An interesting idea is to draw a line between each circle when they collide. This forms a kind of node based structure between circles, creating a network where larger circles hold more power in the network. I wonder if you could create a page ranking system based on something like this...?

Benoit Mandelbrot - Fractals and the art of roughness

2010-07-06T15:07:00.001-07:00

A personal hero of mine talks about fractals.

I enjoyed his quote at the end and found it quite relevant to a lot of the work I do on this blog:

"Bottomless wonders spring from simple rules... repeated without end"

Computer Vision and the Hough Transform

2010-07-02T03:35:00.000-07:00

I was working on computer vision yesterday and went to my girlfriend's graduation ceremony today so haven't had a chance to upload. I decided to take another look at computer vision - and in this case a slightly more intelligent one than previously. The method I took a look at is known as the Hough transform. I think that the simplest and most effective way to explain how the Hough Transform works is using a bullet pointed list, but before I begin you should know that it is used to extract information about shape features from an image. In this case a line / all the lines present in an image.

We start with an image in which we want to detect lines:

First of all apply a Canny Line Detector to the image isolating edge pixels:

At this stage, to reduce computation required in the next stage I decided to sample edge pixels instead of using all of them. The results for s=0.2 and s=0.9 are shown below:

Then, for every possible pair of sampled edge pixels, calculate the angle of the line between it, as well as the distance to the origin. Plot a cumulative bitmap graph of angle against distance. The way I did this was to increase the pixel value in that location each time a distance/angle occurred. Recall that a line can be defined by an angle and distance to an origin. The resulting bitmap is known as the Hough Transform:

By increasing contrast and playing around with thresholds in the Hough transform it is clear that 8 distinct regions are visible, we know that the detector has done its job as there are 8 lines in the original image:

Remember that each point provides us with data about the line angle and distance from the origin, so lets use the flash API to draw some lines:

As you can see the result isn't too bad at all, we get 8 lines, although they are a bit diffuse. The next step is to look into grouping algorithms to only pick single pixel points from the final hough transforms for each lines. In this version of the program a line is drawn for each pixel, which results in an angle and position range for each line. Pretty close though.

So thats how a Hough transform works for line detection. Just for fun, heres a real time hough transform on a webcam stream. Just click the image below to launch it.

Generative Art

2010-06-30T08:39:00.000-07:00

Just thought I'd have a quick look at creating some generative art after reading Karl Simms' paper on Artificial Evolution for Computer Graphics. Images are created by randomly acting various functions on a bitmap in some predetermined order. Functions might include gradients, convolution filters, shapes amongst others. At this stage I have only made a black and white version of the generator, but I'll look what I can do about a colour one sometime soon. Just click the first images to launch the app, click and click again to stop/start the generator. If you find some cool images just take a screenshot and email them to me.

Physics Evolution: Step 1

2010-06-28T13:50:00.000-07:00

After a bit of a post exam break I'm back to my desk and playing around with some projects that I've had to let lie for some reason or another over the last few months. The first one I thought I'd look at again was the Creature Evolution in Flash article I wrote a few months ago. Back then the idea was to write a program that would evolve creatures using genetic algorithms. Today I've been working on the first step namely creating a world within which these creatures should be able to evolve. This requires a physics engine and instead of writing my own from scratch, or using something I've made before I decided to go with an efficient, fast, and reliable engine, APE, by Alec Cove. You can download the API here.

So I've been getting to grips with the engine which seems fairly simple to use and here is a little demo:

So what is next? The idea behind genetic algorithms is that some genotype, in this case a string of 1's and 0's, determines a phenotype, in this case the structure of a creature. By randomly mutating bits in the genetic code, and testing the resulting creatures against one another, and sticking with the code that yields the best results, creatures can be made to evolve. Creatures can for example be tested for their ability to run fast, or for their ability to jump, or to swim.

Ideally I will reach a stage where code can be saved at any stage of the process, and can be emailed to another person somewhere else in the world who can continue to evolve the same creature. Obviously since evolution is random there could be some very interesting splits. It would be nice to create a sandpit where creatures could be watched. A further investigation would be the effect of mating genotypes to create hybrid creatures, and obviously the nature of the algorithm used to produce creature structure would determine the success of this.

Anyway stay tuned for progress!

Von Neumann Cellular Automata

2010-06-22T02:13:00.000-07:00

I just saw the TED talk from Stephen Wolfram below and noticed I'd never written any 1D cellular automata. He briefly mentions rule 30 and the emergence of complexity from a simple set of rules. The Von Neumann automata is very simple to write. Given a single cell, the state of the new cell (either on or off) is determined by the cells in its local neighbourhood. In one dimension this means the state of itself, the cell just to its left, and the cell just to its right. This means there are 8 possible states for local neighbourhoods (8 rules) and therefore 256 possible outcomes of the system.

As Mr Wolfram mentions in the talk, most of the outcomes are not particularly interesting, some are very plain and some are quite pretty. Below is rule 26, it looks nice but beyond that it is quite a simple rule. Self repetition on a number of different scales is pretty much all it is capable of. Just click the image to launch it.

The next two examples are rule 30 and rule 110 respectively. These are extremely interesting. Rule 30 displays what Wolfram calls "Class 3" behaviour, which is a chaotic and seemingly random, whereas Rule 110 displays "Class 4" behaviour, which is neither completely random nor completely repetitive. The interaction of various local structures is used to prove Universality. Again just click the images to launch the programs!

Rule 30 can be used as an excellent random generator:

Notice the life-like region travelling up near the centre in Rule 110:

Galaxy

2010-05-31T05:37:00.000-07:00

Just a little fun one because I've finished my exams and I haven't had time to start any big projects yet. A bit of very simple inverse square law gravitational physics to simulate the sombrero galaxy. All orbiting stars are attracted to the centre of the galaxy by an amount proportional to 1 over the square root of the distance between them.

Just click the two images below to launch the 2D and 3D simulations! Enjoy.

The three examples below show that with slightly different initial conditions, the shapes we find in a simple galactic simulation like this one, are actually surprisingly similar to those we see in real galaxies, for example in the first you can almost see the emergence of the spiral arms of our own galaxy the Milky Way.

Self Painting Images in Flash

2010-05-27T06:15:00.000-07:00

Leading on from the previous post I decided to automate the painting process. The brush moves around the screen randomly creating a stipple like effect by increasing and decreasing pressure. Take a look, its really quite hypnotic. Just click on the image below to launch it.

Wet Paint Mixing in Flash

2010-05-26T18:01:00.000-07:00

One of my favourite features on Photoshop CS5, is the wet mixer brush, which is almost like a real paintbrush to use. I decided that if photoshop could do it, so could I, and a started to work on writing some actionscript that would handle the job.

The basic idea is that a brush is made up of bristles. When you press down on the screen each bristle picks up a certain amount of paint from the pixel it is currently over, and then as you drag your brush around, each bristle drags paint around underneath it.

To do this I wrote some actionscript that found the colour under each bristle, mixed the paint that was already on the bristle with the new paint underneath it, and then moved that new colour to the new location of the bristle. The program draws the paint stroke onto a new layer, a kind of buffer, which it then blurs (for added realism) and copies back onto the original painting.

Here are a few initial results:

Original Image

Painted version:

And here are a few more examples of another image created with it. I'm actually getting similar results as with the photoshop brushes which I'm quite pleased about. To launch the application simply click here and give it a go for yourself. Let me know what you think!

Attempt at "fast" solution to the N-Body Problem

2010-05-15T14:43:00.000-07:00

The N-Body problem is a very interesting problem both mathematically and in real world applications such as in observational cosmology. The basic idea of the N-Body Problem is, given N gravitationally interacting bodies, what is the most efficient way to solve the subsequent motions of all of the bodies given some initial conditions? I will be looking at the problem in 2 dimensions.

Lets first take a look at the example in its simplest form, with just two bodies. The two bodies pull on each other by the gravitational force, which causes both to accelerate along a vector pointed along the line joining them. This is a very simple problem to solve and any university level physicist should find solving it trivial. In the case of more bodies however, an analytical solution becomes extremely complicated and far beyond the reach of my mathematical understanding; but what I do understand is computers and iterative techniques. The simplest way therefore to solve a problem with more than two bodies would be simply to summate the forces of all the bodies acting on one body at a given moment in time and update its velocity, then repeat this for each of the other bodies in your system.

Obviously for a number of bodies N, the number of force checks that would have to be done would increase very quickly, in fact at a rate N*N, which means for 1000 bodies, 1 million checks would have to be carried out, remember this is per instant in time.

I propose a solution that uses the bitmap functionality in flash, along with the blur filter. I am sure that it won't stand up to rigorous mathematical scrutiny, but from an aesthetic standpoint, it does the job near enough ok.

The idea is that each body is represented by a pixel, with a colour related to its mass. By applying a blur filter on the bitmap, the gravitational field of the pixel is extended into the surrounding region. A brighter region means more gravitational force, and a darker region less. To solve the problem particles simply need to be accelerated along the line of highest gradient towards brighter regions. This way only N checks have to be carried out massively decreasing computing time.

For example carrying out the test with 10,000 particles, which would otherwise kill my computer (at 24 frames per second that would be 2,400,000,000 force checks per second!) it actual runs reasonably well!

Anyway take a look and feel free to make suggestions to improve the model. Just click the first image to launch the simulation!

Note: Limitations of the simulation include -

Blur is not complete, i.e gravity has a limited range - this may be analogous to simulations of the large scale universe where distances are two large for information to pass between.
Blur takes multiple steps to update (slow information rate)
Singularities such as collisions cause erratic behaviour (sudden velocity boosts)

Further Note: "Universe" has periodic boundary conditions, i.e X = X + Width & Y = Y + Height

Update: Running the simulation with more particles (100,000) without periodic boundary conditions yields interesting results. As expected the "universe" collapses in on its centre of mass. In this simulation I increased the blur distance, i.e the range of gravity, producing less local effects. The second image shows the simulation after it reaches a stable state with a large central mass.

Pedestrian Playground

2010-05-14T02:52:00.000-07:00

Looking through one of my favourite books, Critical Mass, I came across a page I had been meaning to do some research into. The section of the book was on cellular automata, and the creation of complexity from simple rules. I mentioned a few posts ago about a paper I had read about solving the Travelling Salesman problem using ants. The travelling salesman solves the problem of getting between a number of towns using the shortest route possible. This is all well and good but the travelling salesman has an absolute answer, and in my opinion that immediately makes the problem slightly less interesting. The randomness of the human psyche is far more exciting, and the pedestrian motion created when you bring large groups of people together are often quite surprising. Take a look at the image below for example; the trails connect 3 points of interest

around a park. None of the paths join any of the 3 target locations in the most efficient way, yet after years of trampling down grass, and the slow fading of former trails, the most desired route (on average) is the one seen here.

Obviously park planners would have a much easier job keeping their lawns meticulous if they could somehow predetermine where people were most likely to walk, thus keeping pedestrians on the paths, and not trampling their grass. This problem is slightly more subtle than the travelling salesman, there are in fact many solutions and they depend on a huge number of factors: how many people want to go to each destination, how fast does grass regrow, how fast does a path form, how many people commute along the paths each day, do people have to walk uphill, is there a fence...? Obviously the list goes on for quite a while, after all humans are not predictable, but we can still create a simple model.

The screenshots below show the main interface of my application, just click the first image to launch it. The number of target towns, and the number of people can be changed, as can the size of random fluctuations in direction, the effect of the destination on the direction walked, and the effect of the route on the direction walked. Two factors called visibility, and distance factor also affect the likelyhood that a pedestrian will take the most direct route to their destination. Have a play around with the factors and see if you can reproduce the pattern seen above.

In the below examples you can see paths merging, even though this is not the most efficient route for anyone. The first image still has some "visibility", the second has absolutely none, people just tend to congregate randomly, but it does make a nice pattern, and the third shows path splitting, where two similar but separate routes form spontaneously.

Nice Little Cloud Effect

2010-04-12T10:09:00.000-07:00

Came up with a nice little moving cloud effect great for flash sites. The cloud texture was created using photoshop, and the Render -> Clouds, and Render -> Difference Clouds filters. Using the blur tool I created repeatable tiles then transferred the images into flash. The movie consists simply of two cloud images scrolling at different speeds, scales and transparencies. Another nice feature is that the movie is fully resizable up to almost any scale - within reason.

Just click the image to try it out!

Zoom Quilt

2010-04-05T04:30:00.000-07:00

I remember seeing this years and years ago, around the time I was first getting into flash. Looking at the date it was made in 2004. The project known as the Zoom Quilt, was a collaboration between various artists and is a beautiful illustration (excuse the pun) of what can be done in flash. Click the image to run the file, and use the mouse to drag in and out of the quilt.

Travelling Salesman Problem

2010-03-26T08:36:00.000-07:00

I have been extremely busy over the last few weeks with various University projects, so the genetic algorithm work has moved to the bottom of the stack. The ideas and problems are still quite fresh in my mind, so without going straight into programming the physics based evolving creatures, I'm going to have a look at something else quite closely related. It is linked in to both evolution and optimization. There is a very old mathematical problem, known as the travelling salesman problem (TSP). The TSP involves finding the shortest route between a number of cities, visiting each city only once.

Finding fast solutions to the problem is vital for applications such as route finding on maps. Anyway, I recently read an interesting paper one approach to solving the TSP ( Ant colonies for the traveling salesman problem ). The paper shows that using ant agents, which lay virtual pheremones, a shortest path can be found. Ants prefer to follow paths with more pheremones on them - this means that shorter paths will build up more pheremones because more ants will travel along them.

When I get back to my computer I will have a look at creating a similar solution to the problem in flash, and see the kinds of results that can be produced.

It might also be interesting to look at the effects of changing the properties of ants on how well the system optimizes itself.

I'll get back to you with any results!

3D Experiments - New Toy

2010-03-16T10:00:00.000-07:00

I've been quite excited at the moment, playing around with my new toy Cinema 4d.

Here are some of of the first things I've made - click the images to run the videos. The first uses bullet physics and the second uses Cinema's hair plugin.

Enjoy!

Creature Evolution in Flash: First Thoughts

2010-03-07T15:03:00.000-08:00

Simple 3D Music Visualizer

2010-03-06T14:02:00.000-08:00

Just played around a bit with the 3D fluid dynamics thing I made a few days ago. I added some computeSpectrum functionality using the Flash 10 audio features and created a very basic music visualizer. I'm not entirely happy with it but its worth a post, just click to start it up (the song might take a while to load):

The song is "Rabbit In Your Headlights" by Unkle, enjoy!

Image Evolution: Madame Mattisse

2010-03-06T03:27:00.000-08:00

I've come back with a new and improved evolution algorithm, one which doesn't stop evolving after 300 generations! I've also uploaded the movie with a bit of a UI which you can have a play around with and see how well you can evolve the images. The ones below show the kind of evolution you might be able to achieve. I've also changed the fitness function image to one of my favourite paintings of all time, Madame Matisse, by Matisse. Just click here to launch the movie.

Enjoy the Genetic Algorithm fun!

A Brief Look At Genetic Algorithms

2010-03-05T14:07:00.000-08:00

This post is sort of a continuation of my work on natural selection and evolution as a tool for image compression. Genetic algorithms are an extremely interesting area of study, and over the next few weeks I'll be exploring the kinds of things that can be achieved in the field using actionscript and the flash player. Genetic algorithms are being used to evolve some of the most advanced robots in the world, as well as being used in route finding and compression applications.

So what is a genetic algorithm? In a nutshell it is a computational technique through which solutions to optimization problems can be found. It is an evolutionary method that can be compared to the way evolution and natural selection work in the biological world. A genetic algorithm requires two things to work, a genetic representation of the thing you are trying to evolve, and what is known as a fitness function to compare your genes against.

Lets take the example found in the video below (click the image and it should start up):

Each creature is represented by a set of genetic data. This determines everything about that creature, how big it is, where it has joints, any muscles it might have and how it decides to use them and so on.

By comparing the phenotype (the physical outcome of the genes) to a fitness function, we are able to determine how suited a certain version of the creature is to performing a certain task. Examples of fitness functions include the ability to swim fast, the ability to jump, or the ability to win in a game of football.

Currently there is no evolution going on at all, so we need to introduce random mutations in the genetic data. You should be able to see that a random mutation might cause a creature to be more effective at carrying out the fitness function, if it is we can stick to the new set of genes, otherwise lets go back to the original.

In my program to evolve an image from a few polygons the fitness function was the similarity to the comparison image.

So now that we've discussed computational genetics briefly, how am I going to work this all into a flash project. The first issue is creating a physical world in which my creatures can evolve. Clearly I don't have the computational power to test millions of creatures in 3D with a 3D physics engine, so that isn't an option. I have decided to stick with a simple 2D Verlet Integration based particle engine with constraints and muscles (no line-line or polygon-polygon collisions) and see what happens.

I am quite excited about seeing where this one is going to go, so stay tuned!

Image Evolution

2010-03-03T13:23:00.000-08:00

Based on the work by Roger Alsing I thought I'd create a real time evolving image. Initially 30 random numbers are generated from a seed, these numbers are the components of the DNA strand. Each number corresponds to a specific polygon with a characteristic colour, transparency and number of vertices. A mutation in the DNA strand results in a shape changes. Images before and after a mutation are compared to the original painting, Girl With A Pearl Earring, and if a mutation causes greater similarity, then the mutation holds, otherwise the DNA reverts to its previous form. This is similar to how evolution works in the biological world.

Here are the first few mutations showing development of the image:

These are early stages, with up to 165 successful mutations. I will leave the program running over night, and will update the results. The lack of computational power in AS3 and my completely un-optimised code means that comparison processes take quite a while. One way to improve speed would be to reduce canvas size so I may turn to this if the program doesn't produce anything nice.

Having said that the early results are making me feel optimistic. We just need a few more thousand mutations and it'll be there.

Update: Here are the 198th and 238th mutations, I don't think the image will look that interesting until it gets into the 1000s. Its getting there but its clear that its a long process. Unfortunately the rate of improvement also slows down. Its up to about 15000 mutation attempts, and its taking longer and longer to mutate successfully each time. Currently only up to 10 vertices are allowed per polygon. Increasing this maximum number to more could increase the rate of improvement. As could allowing other sorts of mutation such as gene swapping, where two of the seed numbers swap. I'll give this a go soon although I will let this version go to 1000 mutations just to see the results.

Update: Just a though on using this as a compression technique. Each seed number is a 32bit integer. This means 30 numbers comes to 960bits or 120bytes per image. Given that the original version of the image I used (a PNG so already compressed) comes to 231kBytes, thats a compression factor of about 2000. Even using 100 polygons (a factor which would drastically improve the final evolution of the image) the compression factor would still be around 600! This is very impressive. I remember reading about a competition somewhere to send images as twitter messages (a twitter message contains up to 120 characters or 120bytes of ascii?) This means that the images I have produced could indeed be sent as twitter messages.

Update: The evolution process seems to be levelling off at about 360 successful evolutions with over 1.6 Million evolution attempts. This leads me to believe that my evolution parameters weren't ideal. The two images below shows the image as far as I'm going to take it. The second shows a blurred image applied and actually the result is pretty good when compared to the blurred original (in other words when you squint you should be able to see the original image. I'll come back when to you when I've improved the parameters and algorithm slightly!

3D Waves: Projected 2D fluid simulation

2010-03-03T08:17:00.000-08:00

I found this experiment quite interesting. In an earlier post I gave an example of a 2-dimension fluid simulation that I'd been working on using the Navier-Stokes equations. I decided to play around with this code a bit and use the 3D point engine from my last experiment in conjunction with the fluid engine. The density from the fluid simulation is simply projected onto the XZ plane with density values corresponding to the height of corresponding point particles.

The results are certainly interesting. Click the image below to start up the experiment. To create waves just move your mouse around and drag the movie to change the camera angle. I decided to add a slight fade and blur on the particles which makes it look very pretty. Enjoy!

OBJ Vertex Renderer

2010-02-24T10:26:00.000-08:00

Just a really simple and quick experiment, to see if I could load a Wavefront .obj file into a flash movie and render the vertex co-ordinates in real time, in three dimensions. Just click the image below to launch the experiment. The object contains about 30,000 vertices, and these are simply transformed from 3D to 2D space and displayed using bitmap data. This is nowhere near as complicated as my prior attempt at a 3D engine, but I decided to make performance more of an issue this time. It does run at full frame rate quite happily on my computer. Let me know about your experiences.

The next step is an edge renderer (wireframe), then a face renderer. We'll see how high the performance can stay. Obviously the ideal case is a high quality raytrace in real time with shadows, reflections and more, but lets not kid ourselves.

Image Transform Tool

2010-02-23T15:41:00.000-08:00

I've just been playing around with this little class made by Ruben Swieringa.

It allows any image to be transformed by providing any four corner points. In the demo I used an animation of mine (Strange Attractors).

Click on the image to begin then try dragging around the corners. I'll see if I can come up with any other experiments using this neat class. Any bitmap data can be used, so videos, images and animations can all be dragged around in 3 dimensions....

Face Recognition Algorithms

2010-02-18T04:10:00.000-08:00

Over the last few days I have been looking at a various algorithms and methods used in face recognition processes. The first method I looked at uses a colour space known as TSL (closely related to HSL - hue, saturation, luminosity). This colour space was developed with the intention of being far closer to the way the human brain sees colours than RGB and other computationally preferred systems. Taking a webcam stream and converting all pixels into TSL colour space with [R,G,B] -> [T,S,L], I found that although in certain lighting conditions the system can differentiate between skin colour and other surfaces, the method is far from ideal. For example the cream walls in my house can often be identified as skin colour, which clearly shows an issue. It is also clear from the images that areas of my face that are in shade are not recognised as skin. These issues are best addressed using methods that do not depend on colour.

In my research I found two viable methods for use in face recognition, using eigenfaces, and fisherfaces.

Eigenfaces seemed to be a more commonly used method, so I decided to follow that route first (albeit roughly, as I'm sure you all know by now I like to do things my own way when I program). In order to recognise a face in an image, the computer has to be trained to know what a face looks like. The first step involved writing a class to import .pgm files from the CMU face database. Here is a sample of what the faces looked like when imported. All images are in the frontal pose, with similar lighting conditions, and varying facial expressions.

The next three steps involved creating an average face, and taking the resulting image and calculating it's vertical and horizontal gradients. The average face simply sums all of the pixels at each location for each face, and takes the average value. To calculate the gradient the difference between two adjacent pixels is taken in either the vertical or the horizontal direction. Computers find it easy to see vertical and horizontal lines (I have already written some basic shape detection software which uses these kinds of algorithms) so I thought this might be a good idea to use these as comparisons with found faces. I planned on using a kind of probability test, with a threshold as to the likeliness that any part of the image is a face, by comparing it to the mean face, the horizontal gradient face, and the vertical gradient face.

The three faces found are shown below for this database. Clearly one could find the mean face of all people wearing glasses, or all men, or all women, and this would affect it's final appearance. Therefore it could theoretically be simple to build in gender testing using webcams (assuming a complete lack of androgyny which clearly there is not....), but a probabilistic approach could still be taken.

The mean face looks incredibly symmetric and smooth. This is perfection folks, and its kind of frightening! The idea behind using these for face recognition is relatively simple. Scan an image taking the difference between an overlaid mean face, and the region of the image being scanned. If the difference is below a threshold it means that the images are similar. This means it is likely that there is a face where you are checking. To ensure it is a face consider the horizontal and vertical gradients of the mean and compare them. If they are similar to within a certain threshold it is very likely you have found a face!

I'll come back to you when I have some working flash files and source code!

Three Dimensional Projection

2010-02-09T11:08:00.000-08:00

I came across a very interesting video recently. A design agency from the Netherlands called NuFormer Media have mapped various famous buildings in 3 dimensions. Using the three dimensional data, images can be projected onto the building, with amazing accuracy. The results are amazing and quite hypnotising, I especially like the crumbling building at about 36 seconds in. Just watch the video below!

Followers: 20,000 particles

2010-02-04T16:09:00.000-08:00

I've been playing around with vectors and decided to see how many particles I could get to follow my mouse using bitmap data. Using 300,000 particles (nearly half a million) I clocked around 2fps, I decided to add a few more effects (colours, trigonometry for the following etc) and found the simulation to run at max fps up until around 20,000. Not bad at all and some of the effects look really pretty! Here are some screenshots, or just press here to run the app. You can use the slider at the bottom to change the number of particles from anything between 20 and 20,000.

The third picture above uses a blur filter on the bitmap data, some of the visuals created with this version of the program are really beautiful. Check it out by clicking the image!

Chrome Effect Ray Tracer

2010-02-04T14:34:00.000-08:00

Applying a chrome filter to a finished ray trace render creates an amazing effect. Take a look for yourself. I'm in the process of developing online software where you'll be able to create simple 3D scenes and raytrace them with a number of effects; including anaglyph 3D, chrome and a few more! This is my screensaver at the moment:

Road Generation: First Attempt

2010-02-02T15:37:00.000-08:00

I decided to take a look at using Voronoi diagrams to generate road systems. Here are a few very early screenshots! Looks promising.

Terrain Generation

2010-01-29T16:13:00.000-08:00

Time for another post and another experiment. I was just reading an interesting paper called Procedural Techniques For City Generation by some chaps in working at the ITB in ireland all about how to generate completely algorithmic city plans given a starting point and a landscape to build on. The image below shows an example of some of the stuff that can be produced with these algorithms and it truly is amazing!

Anyway I thought I'd step back a bit and try to produce some of my own landscapes to start with, and then move onto road generation and finally buildings. Its always nice to start with the easy stuff, that way I find at least I get something done!

Since the actionscript random function generates a new random seed each time a program is run I decided to use a custom random number function which could take a seed. The generator I used is the Park-Millar-Carter PRNG which is ideal for the job. I like the idea of using words (like in the original worms) as seeds so using an input string, eg "Terrain1" and then taking an MD5 hash of it, converting this into a number provided a constant seed for a word. The seed would generate every piece of information in the same way every time, very useful when you find an interesting image.

So I built this in then created several layers of bitmap data, each with different resolution with each pixel on each grid set to a random value (in the range [0,0xFF]). The resulting addition of all the bitmaps would produce the data for my final landscape. Here are a few examples of the kinds of landscapes I was able to produce:

To me the third image is a spitting image of europe, with spain, germany and france and even the UK to the very top left! I'm quite happy with the results all in all. To try out the app for yourselves just click here, enter a keyword, and press generate!

Next Step, build some roads!

Anaglyph Raytracing

2010-01-16T09:49:00.000-08:00

I made a few changes to the raytracer I've been designing to create anaglyph images, that is two channel 3D images. The changes are very simple, literally two black and white images are drawn from slightly different angles, then one is tinted in cyan, and the other red. I don't have any 3D glasses but it should work. If anyone has some check out the test image below!

I'll try to produce some more images like this and get a pair of glasses to test with. Imagine realtime anaglyph raytracing!

New! - Recommended Books

2010-01-10T12:50:00.000-08:00

I've got together a list of books related to flash and learning AS3 you might like. These will permanently stay in the right column but right now here are a few of my favourites:

As a general guide to getting started in AS3 the following is great. I would recommend it for beginners though:
Essential ActionScript 3.0 (Essential)

For anyone interested in game design this is a fantastic and comprehensive guide:
ActionScript 3.0 Game Programming University

More on the theme of this blog one of my favourite books of all time. The Author Phillip Ball discusses connections between the natural world and various mathematical models that describe them. I still find it a great source of inspiration for various experimental flash projects that I have worked on recently!
Critical Mass: How One Thing Leads to Another

Like I said from now on there will always be a list of books to the right!

Get reading folks :)

How To Build A Raytracer: Part II

2009-12-30T16:32:00.000-08:00

In the previous post we looked at some of the fundamental ideas behind raytracing and saw some stunning renders created using the technique. In this post we'll start to take a look at the camera, and how to create a three dimensional scene.

The Camera

To start with lets create a camera at a position in space [camX,camY,camZ]. This camera can move up, down, left, right, in and out around your scene, and is where all of the initial rays are fired from. The image below shows how the rays exit the camera through the scene. It is clear that we want our rays to pass from the camera through the image, as shown in this diagram, but how do we find these rays! For a horizontal camera with no rotational properties this is actually very easy, so lets take a look at how to do it.

Traditionally cameras have a property called the field of view. This is related to the range of angles that a camera can see. A fisheye lens, for example, has a large field of view (180 degrees?). High field of views can result in image curving and I've found that the optimum angle between the horizontal and the top vertical for ray tracing is around π/6 degrees giving a field of view of π/3 or 60 degrees.

Once we've decided on a field of view for our ray tracer we can determine the distance between the image plane and the camera. Remember, unless the image is completely square the field of view in the vertical range and the horizontal range will be different. Programmatically, creating a new variable called the scale of view makes things far easier where:

var scaleX:Number = Math.tan(fovX);
var scaleY:Number = Math.tan(fovY/(scenewidth/sceneheight));

In the above actionscript, scene width and scene height are the pixel height and width of the image you want to create. Once we have our scales of view we can start firing rays. In a ray tracer rays are fired through every single pixel in the image. Although it results in pixel perfect images the computation required can also be rather large for high resolutions. This is why ray tracers are not currently used in real time applications.

So the next step in the ray tracing algorithm is to cycle through each pixel creating rays. I suggest using two embedded for loops although there are other ways of doing this depending on the structure of your program:

for(var i:int = 0; i < scenewidth; i++)
{
   for(var j:int = 0; j
   {
   rayX = scaleX*(2*i-scenewidth)/scenewidth;
   rayY = scaleY*(2*j-sceneheight)/sceneheight;
     rayZ = 1;
   // After we have created the ray we calculate collisions - and then render the pixel
   }
}

The above is a simple example of creating all the rays needed for a scene.

In vector mathematics a lot of calculations rely on the vector being unitary (meaning of length 1). To fix this just take the modulus of (rayX, rayY, rayZ) and divide each of rayX, rayY, and rayZ by this modulus.

This simple model can be extended by adding yaw and pitch, and for the really enthusiastic even roll! These are 3 types of rotation. The simplest way to create rotations is to rotate the ray vectors around the camera's location once they have been generated using matrix transforms. This will fit into a later tutorial.

Stay tuned for the next in the series soon!

How To Build A Raytracer: Part I

2009-12-30T09:22:00.000-08:00

This is the first of what I hope to be a few posts that describe the fundamental theories behind building a raytracer. I will specifically look at how to build one in flash using AS3, but the theories should be easily transferrable to any other scripting language so whether you use C++ and openGL, Java, Python or AS3 this set of tutorials will point you in the right direction.

This is not just source code that I'm posting up, I will describe everything that I feel is needed to build a ray tracing engine without necessarily giving too much code. In the end I feel this is a far more rewarding way of learning flash and creating new projects, and is how I have taught myself in the past. Certain aspects of maths throughout the tutorial may be of a reasonable level but most high school vector course books should give enough knowhow to be able to see what is going on. So lets begin.

Note: the image to the right shows the kinds of lighting effects a raytracer can produce.

What is a raytracer

In nature a ray of light travels from a light source - interacts with some objects and either disappears into space or reaches our eyes. What we see depends on what the ray has collided with on the way to our eye. For example taking a light source to be the sun, trillions of rays hit earth every second, each of these reflects, refracts and is absorbed by trees, by roads, by cars and by other people. For us, the onlookers, only a tiny fraction of these rays hit our eyes, but when they do, the individual rays (photons) create the scene we see in front of us on the back of our eyes ready for our brains to untangle and interpret.

The idea of a raytracer - at least in the sense of this tutorial - takes what happens in nature and reverses all of the processes. Rays are created in the back of our eyes and are fired in a range of directions at our scene. Each ray passes through a point in our image and will either pass through our scene or hit an object. The image to the left helped me understand the ray firing process. When a ray hits an object there are 3 possibilities:

(i) The ray absorbs the ray
(ii) The ray reflects the ray
(iii) The ray refracts the ray

In the first case, a new ray is case from the point where the ray scene collision occurred, in the direction of any light sources in the scene. If there are no objects in the way then the object is lit, otherwise the object is in shadow.

In the second case a new ray can be cast depending on the surface normal of the object which can interact with the scene again. The ray can keep colliding with objects up to an arbitrary number of times so theoretically a ray could bounce between objects forever.

In the third case a new ray can be cast depending on the surface normal and refractive index of the material. As above this ray can continue to interact with the scene.

These three cases are not mutually exclusive. In a scene there can be any amount of refraction, refraction, absorption and shadowing, which gives ray tracers their realism. Take a look at the top image for examples of all three, and the image by pixar below is another example.

We've seen that a raytracer is just a way to render a scene which is physically realistic and can produce effects like shadowing, reflection and refraction in a far simpler way than many other rendering methods.

In my next post I'll explain how the camera works and how to set up our first scene.

My Fluid Dynamics Engine in AS3

2009-12-30T04:44:00.000-08:00

This post and my recent experiments have been inspired largely by the work of Eugene Zatepyakin and that of Jos Stam on fluid dynamics.

Jos Stam's article on fluid dynamics for games started it all, having a similar effect on this area of research as Thomas Jakobsen's article had on the use of Verlet Integration in physics engines. The beauty of the fluid solver is that it provides a computationally quick and stable approach to simulation of fluid dynamics, which can be easily expanded into 3 dimensions and used to solve many more advanced problems.

Eugene Zatepyakin was the next step in the chain creating a fast engine in AS3 which I talked about in a previous post. I decided to write my own version of the engine and here it is:

The first example shows 4000 particles floating around in the simulated fluid - just click on it to launch to flash file - once it is running click and drag to make the fluid move.

The second example shows the pressure grid being used as a displacement filter for the image below. This starts to add a bit of realism and creates a more three dimensional feel.

Flash Ray Tracer Reflections

2009-12-16T11:08:00.000-08:00

Finally managed to get reflections properly working in my actionscript raytracer. The mathematics behind reflections is very simple. Given an incoming light ray V, and a surface normal N, we can calculate the reflected light ray R using:

a = V.N
R = V + 2*a*N

I applied this theory to the ray tracer and the results are beautiful. Its amazing how much realism a few shadows and reflections can create! The number of reflections obviously changes the image realism. The images below show 1, 2 and 3 reflections per ray. Surprisingly there really isn't much of a reduction in performance - and for the purposes of a flash raytracer 3 reflections should be plenty!

Just need to add some functionality for box reflection and then I'll set the engine rendering some nice scenes!

One further extension I might set myself is diffuse reflections. Instead of light being reflected directly along the normal, there could be random fluctuations in the reflection vector. I think this could produce quite a nice wave effect. I'll keep you posted!

On a performance note the image with 3 reflections took just over 2 minutes to render in 1600x1600 with no real optimisation. For a resolution of 400x400 pixels it takes about 2.5 seconds. Not too bad at all in my opinion!

Update: Here are a few fuzzy shots. The first one is less fuzzy and the second one is more fuzzy. Quite an interesting effect I think:

Decided to go a bit mad and rendered a rather large image with a load of boxes and reflective spheres. Inspired by SuperJers PixelMachine, but rendered completely using flash and AS3, not OpenGL and C++. Here it is (Something has gone wrong with the reflections of the boxes - there is no shadowing - but I didn't have the heart to stop it once it was half way through!):

Here is another nice one, 2880 by 2880 pixels, back to the original room but with the reflection stuff added. Looks quite nice in the super high resolution!

Update: I've rendered few more large reflective images - there is still something slightly wrong with the reflections I think, check them out:

New Raytracer Features

2009-12-15T09:17:00.000-08:00

I've been working on this now that term is over. The features I've added are diffuse shadows - multiple directional lighting - and box rendering. Here are a few renders. In order they show a low resolution diffuse shadow render, a high resolution render with a cube, and a high resolution render without global lighting with two point lights:

And here is a render I like with 4 lights:

Update: Deciding to take the whole concept a bit further and show you that the ray tracer is not just good for rendering spheres and cubes I rendered a really simple office scene of some description - here it is:

Update: Finally started looking at reflections. I've got the maths bit of it sorted. Just got to look at the way I'm structuring my code to help it make a bit more sense. Here is my first result, to show that the angles work!

Update: Same again but this time with 50 or so spheres floating around in the sky - and a reflective floor. Nice to see it almost working!

New Scientist Features the Mandelbulb

2009-12-15T05:19:00.000-08:00

I discovered an article in the latest New Scientist magazine about Daniel White's Mandelbulb. Found it really cool as I've been working on this stuff quite a lot recently! Read the whole article here at New Scientist!

Quick example of real-time raytracing in flash

2009-12-11T08:38:00.000-08:00

Just a quick low res, and completely un-optimized example of an animated version of the ray tracer I've been working on. The light source moves in real time and you can move the camera around with the mouse.

Just click the image below to launch it!

Plane Intersections Added to Flash Raytracer

2009-12-04T10:16:00.000-08:00

I was working late on this last night when I should have been doing coursework. Anyway I managed to get plane intersections in the AS3. The maths was actually very simple. I'm still working on reflections so stay tuned! Below is a nice example of spheres and planes being rendered. Total time about 15 seconds, 1100 x 800 pixels.

First Screenshots of my AS3 Raytracer

2009-12-01T15:06:00.000-08:00

After writing a really simple ray tracer to render the Mandelbulb in my last post, I thought I'd write a slightly more advanced one, with more accurate shadows, reflections and all things nice ray tracers have.

I started just getting the raytracer to draw some spheres, but the results weren't very pretty. I added some shadows and some distance based lighting and they began to get a bit better.

Anyway here are the first screenshots. Once I'm at a stage where I'm happy with everything and know that I understand it I'll write a tutorial covering the fundamentals.

First image rendered with shadows - no distance lighting but shadows work

Another similar example

Trying to get distance decay of lighting intensity but using the wrong vector. This causes brightness where there are more spheres for some weird reason!

Fixed it - Shadows look good and added a load more spheres!

I'm starting to like this!

So the next step for this is reflection. This just involves firing another ray when a collision is found and checking for collisions. For those who are interested the resolution is 1100x800 pixels, and the images render in about 5 seconds. Not too bad at all!

Stay tuned for updates.

Update: Just a thought, I think altering brightness depending on the direction of the normal of a plane to the light source would increase realism, also create effects like specularity, I don't know but I'll give it a go and post some screens of it!

Update: Here are a few shots of directional lighting in action! I have to say for such a minor change the realism massively increases. Instead of clear shadow lines, they are all a lot more diffuse! Lovely.

A day time shot:

And at night time - with no global illumination:

Update: Just rewrote almost everything, should make it easier to add new features though. Its looking good, nearly got reflections working, then I'll add some other objects (probably boxes and planes).

Ray Tracer in AS3: Rendering the Mandelbulb in Flash

2009-11-26T01:37:00.000-08:00

So I went off for a few hours and thought how I could improve the voxel engine. Both from an efficiency perspective as well as that of realism.

I realised that the only route was ray tracing and after reading this fantastic article by SuperJer about his pixel machine experiment I was motivated and inspired to try something along these lines for my renderer.

The article takes the creation of a ray tracer from its very early stages to a really polished program. All this happens in one weekend by the way, I really suggest you read it.

Anyway the idea behind raytracing is that a ray of light is passed from your camera through a pixel on the screen. The ray formed between the two points continues to pass through your scene until it hits something. When it hits something the pixel through which the ray passed is updated with the colour value of the object it hit, or failing that the colour of the sky behind, and a ray is "fired" through the next pixel until your image is formed.

So in my case I'm trying to render the Mandulbulb set. Something I've now done many times before, but lets be honest, in the past I've needed huge numbers of voxels and the results weren't great. So what happens in the ray tracer?

1. I fire a ray through the current pixel - starting at 0,0 working all the way to the image width/height.

2. I check along the length of the ray to see if that location is a part of the Mandelbulb Set.

3. If it is - check if that point is in light or shade.

4. Fire another ray from this point to my light source.

5. Check a bit away from this point in the direction of the light source, if that point is also a member then any light from the light source would have been stopped. So shadow the pixel.

6. Otherwise colour the pixel normally.

The resulting images that are built up show a lot more detail. Not only that they have pixel perfect shadowing, perspective, rotation and you can't see any stupid voxels.

Lets take a look below at some ray tracing in flash. Below you can see increasing resolutions from
137 x 100 to 1100 x 800 pixels.

And below is one I left to render for about an hour (2200 x 1600 pixels). Just click to enlarge it!

Radially Coloured Render of 3D Mandelbrot in flash

2009-11-24T15:36:00.000-08:00

Just click to enlarge it! Going to start working on volumetric ray-casting for flash next so that we can get some real shadows in there!

The colours are produced using the radial term of each point in 3D space. For some reason this actually makes it look like there are shadows being cast which is nice, although there aren't. This really brings out a lot more detail in the render!

Inverse Mandelbulb Pixel Mapping in Flash

2009-11-22T13:51:00.000-08:00

When we map the 2d Mandelbrot Set we normally colour a pixel depending on the rate at which that point tends to infinity on some colour scale. In 3D normally this wouldn't work - where you have solid objects you'd be changing their colour internally. But since we are looking at cross sections using the voxel renderer it is actually very doable. Here are a few examples:

Remember that the inverse is being mapped. I really like the effect, and its definitely nice to add some colour to the dull grey images of the previous post.

Its like looking into a three dimensional cave of fractal goodness. Another possibility would be to use transparent pixels and change transparency levels. I will give this a go next as it would allow the whole shape to be seen externally, with colour (possibly? we'll see!) Anyway click here to see all this fractal goodness happening in real time in flash using AS3! Enjoy

Working - 3D Mandelbrot in Flash

2009-11-22T05:41:00.000-08:00

Possibly a world first, I don't know, but I can confirm that I have rendered Daniel White's Mandelbulb set using AS3.

The first render is 216 Million voxels (600*600*600) and took about 10 minutes to do.

This is the 8th order of the Mandelbulb (where things start to get interesting from a fractal detail point of view).

First screenshot is half way through the rendering process:

And here is the finished product:

Hopefully soon I'll have a 3D Mandelbrot Explorer ready and working much like the 2d version previously. I'm currently rendering an image 1000x1000x1000 voxels in size (1 Gigavoxel), and I'll add it to this post when it comes out!

edit: here is the gigavoxel render (zoomed in a bit too much though which I'm annoyed about so it cut off the "colosseum" structure at the top!

here is a quick preview of the voxel engine rendering a lower resolution (400x400x400) version.

To zoom in at the moment you'll just have to right click and press "zoom in" but this won't actually zoom in, just give you can enlarged version. Worth doing if you want to see individual voxels though :)

Enjoy!

edit: Just started playing with zooming and rotating:

Here is a view of the colosseum structure (normally at the top) from the side:

First Demo of the Mandelbulb in flash.

2009-11-18T07:19:00.000-08:00

So I've put together a demo of the Voxel Renderer doing something - not entirely sure if it is the true Mandelbrot in 3d - but click the image below to see the approach I'm taking -

Zoom in and you'll see how it's constructed from isometric cubes.

Mandelbulb - First Thoughts

2009-11-17T15:39:00.000-08:00

In light of Harry's comment I thought I'd take a look at trying to code a Mandelbulb set.

The first obstacle was how to render:

The examples I've seen mainly use ray tracing - there is no way as3 is capable of raytracing this kind of complexity within my lifetime. I decided to write a simple voxel (3D pixel) engine to display the set. The theory behind this is fairly simple. Work in isometry (no perspective), render from left to right, bottom to top and front to back and all should work out.

Just so I knew the kinds of things I was looking for here are a few of Daniel Whites original renders of the Mandelbulb.

So quite something to aim for with flash!

Anyway, I thought I'd start BIG, and by BIG I probably mean I regret doing it now because of the insane render time. Poor flash player.

As I write this the whole render (1000x1000x1000 - 1 million voxels - 1 mega voxel!) is about 2 percent complete. I don't know whether what I am rendering is the right thing or not but hopefully as more shapes begin to unveil themselves it will become clear and I'll know whether to start again or not!

Here are a few renders using the Voxel Engine:

The first few cross-sections - some potential? We'll see..

About 10 cross-sections down - only 990 to go! There are some interesting shapes going on though - note this is a zoom. You can see the individual voxels and how I build them up quite nicely. There does seem to be an awfully regular plane forming which shouldn't be there.

Yet more complete - starting to get some nice inwards curving - hopefully it will make a shape thats kind of spherical...

Just a bit more - about an hour down and the stage I go to bed at! I'll take another look in the morning - until then good night!

Below is what I found the next morning: Not exactly what I was looking for - fractal? possibly - but not nearly as complex as the Mandelbrot I should have been getting.

Unfortunately this means I'll have to change the settings and start over: at least I know the Voxel Engine works, and that I shouldn't do quite as ambitious renders! I'll keep you updated on the results!

Ported Mandelbrot Explorer for Flash AS3

2009-11-11T10:34:00.000-08:00

Hi everyone - I've got some very very exciting news!

I've made a flash version of the project I've been working on at uni with export functionality.

Click here to launch it

The features list is as follows:

Colour Settings
-> Red, Green, Blue
-> Greyscale
-> 3 types of multicoloured rendering

Form Settings
-> Classic Mandelbrot
-> Conjugate Mandelbrot
-> Absolute Mandelbrot
-> Imaginary Absolute Mandelbrot
-> Real Mandelbrot

Dimension Settings
-> 2,3,4,5,6

Preview Image
-> 150px by 120px

Output Image
-> png format
-> 400-2000 width, 300-2000 height

Panning and Zoom - outputted location to interface.

Rendering is never more than about 20seconds even for 2000x2000 pixels on my 2GHz 2GB iMac which is pretty good considering its flash!

Here is a little render of a Burning Ship Fractal at (-1.88480, -0.00041) with a zoom of 126988x. Just click to view it full size!

Outward zoom of embossed fractal!

2009-11-09T13:52:00.000-08:00

Just a quick animation from the application and exported with emboss settings - only 35 frames but you get the idea!

Hi Resolution Mandelbrot Renders - from the Mandelbrot Explorer

2009-11-09T13:28:00.000-08:00

Here are four hi-res images of outputs from my new piece of software - Mandelbrot explorer. The software normally only runs on Windows - but I managed to get it working on my Mac at home using WINE and thought I'd upload some images with various render settings!

Without any further ado - here they are:

Enjoy their high-def beauty!

Again - if you want the app just send me an email!

String Thing

2009-11-08T07:28:00.000-08:00

Just created my entry for the Mochiads 60 second game design contest, its called String Thing - let me know what you think. Just click the thumbnail below to launch the game!