Adrian Boeing: Blog

Kinect viewer with HTML5 canvas

2012-01-12T22:22:00.000+08:00

I wanted to create a web-based Kinect viewer that would work on multiple platforms, including Android mobile phones and iPhones. To this end, I created a HTML5 canvas particle viewer for Kinect data using my very limited javascript knowledge and a lot of Mr. doob's knowledge.

Kinect HTML5 particle image

Take a look at the HTML5 Kinect particle image viewer.

Using libfreenect I captured the depth and color data, used Imagemagik and an Automator script to process and stich the images, and threejs to render.

You can extract data from an image by rendering it to a hidden canvas element, and then reading the canvas image data. To avoid errors, the image data should only be read after the full image has been loaded, as per the callback function in loadTexture.


function getImageData( image ) {
var canvas = document.createElement( 'canvas' );
canvas.width = image.width;
canvas.height = image.height;
var context = canvas.getContext( '2d' );
context.drawImage( image, 0, 0 );
return context.getImageData( 0, 0, image.width, image.height );
}

function getPixel( imagedata, x, y ) {
var position = ( x + imagedata.width * y ) * 4, data = imagedata.data;
return { r: data[ position ], g: data[ position + 1 ], b: data[ position + 2 ], a: data[ position + 3 ] };
}

var texture, imagedata;
texture = THREE.ImageUtils.loadTexture( "textures/sprites/spark1.png", new THREE.UVMapping(), function ( event ) {
imagedata = getImageData( texture.image );
} );

To run the system locally, avoiding some of Chromes very annoying security settings, you can just use python to run a simple webserver:


python -m SimpleHTTPServer

I recorded a short data sequence and rendered to sprites to create this final 3d home move with the Kinect (too slow for my phone to render). I believe this is the first web-based kinect video ever made, youtube3d anyone?

Animated 3D kinect data with HTML sprites

Next time, I might try WebGL...

2011 Wrapup

2012-01-11T21:25:00.000+08:00

Looking back, 2011 was certainly a quieter year than 2010. Personal life got busy in the later half of the year, so less was posted. My job also took a less technical turn as I moved away from software development.
By far my most popular posts concerned my analysis of some popular demo scene effects and WebGL:

The most popular posts were on Ripple effect, Raycasting planes, Twist effect, many more demoscene effects explained.
The self-explanatory demo, was well received, scratching into the top of the month for pouet for a while, and coming 3rd at the Mozzila demoparty. This animates the explanation behind a number of the demo effects.
Slides on a guest lecture that cover some of the details of these effects again.

Otherwise, a survey / summary post on exe compression for multiple platforms was well read, and my Civ 5 casual game mod proved popular too.

I will try to post a bit more about work and the mining industry, not because these are popular posts, but because there is so little information about this field on the web. I hope to post more about robotics and graphics (raytracing), and will try to open source and post about some of my past work.

GPU and Graphics catchup post

2011-12-12T22:11:00.000+08:00

It has been a long while since I've done a graphics related post, so here is a bit of a backlog from the last few months of graphics and GPU links:

Doom 3 source code
Kevin Karsh's work on rendering objects into photos is definitely worth a look if you haven't already seen it.
GTK now supports a HTML5 target.
PowerVR have a great collection of articles, a nice resource to add alongside nVidia and AMD's developer zones.
OpenCL 1.2 was released.
Sfera an open source OpenCL realtime pathtracing game
A great projection onto a building facade in Berlin.
WebCL has been making good progress. Nokia released a WebCL plugin.
Epic Games posted a nice long video of the work involved in creating content for Gears of War.
Fixstars released a short OpenCL programming book
Content for CMU Graphics and Imaging Architectures have been released.
Javascript info toolkit makes awesome visualizations of charts, graphs, and trees.
Progress is being made to run OpenCL on a FPGA by Altera.
Xnormal creates normal maps, and now supports OpenRL.
A nice tutorial on generating texture maps with noise using shaders.
Disney's open source collection has been updated - uv-less texture mapping, scripting/server tools, particle file formats, and the Dynamica Maya plug-in for the Bullet physics engine.
Intel SPMD v1.1 parallel compiler was released.
Intel's OpenCL SDK has seen a number of updates.
Intel Cilk is a new parallel extension for C++.
Cuda performance primitives has reached release 2.0
Adarapi lets you write OpenCL with Java.
A nice description of the GIF file format
A new release of ShaderMinifier to help reduce your shader file size.
GL intercept is a nifty tool that logs all your applications OpenGL calls.
PARSE research group have a number of interesting GPU image processing projects, including Hough Transforms and Speed Sign Detection.
TideArt has interesting graphics related articles and tutorials.

Finally, I'll leave you with a fantastic 64kb demo by Fairlight and Alcatraz that placed 2nd at Assembly 2011.

Remotely Operated Mining

2011-11-29T22:14:00.002+08:00

I gave a presentation on the Transmin Rocklogic rock breaker automation system at the Remotely Operated Mining Projects conference. All in all it was a fairly decent conference focused around the theme of remote operations for mining, focusing predominantly on integrated planning, remote operation technology, and the design and construction of remote operation centers.

Talks were given by:

Greg Lilleyman, Rio Tinto - an overview of remote operations
Matthew Michalewicz, SolveIT - integrated planning for mature organizations, interesting overview of some of the wine industry supply chain issues
Patrick Warrand, Wesfarmers Premier Coal - a open overview of issues for 'small' mining operations (Note: Small is of course a relative term compared to the massive operations of BHP and Rio)
Jeremy Newman, Schneider Electric - a suppliers point of view to automation
Jock Cunningham, CSIRO - an overview of CSIRO activity in mining, and their SLAM technology. (WAMBOT was multi-agent SLAM, CSIRO does automotive SLAM and a novel handheld indoor SLAM 'Zebedee')
Brendon, Leica Geosystems - an overview of Autonomous Solutions Inc (they do lots of autonomous systems for military and agriculture), and Locata - a GPS alternative
David Beck, Beck Engineering - a case study of Simulation Aided Engineering
Adrian Boeing, Transmin - remotely operated rockbreaking
David Cavanagh, Integrated Energy - an overview of remote operation center designs for oil and gas, and mining
Lucas van Latum, Modular Mining - Goal orientated planning and the Observe-Orientate-Decide-Act loop
Reuben Kooperman and Peter Hunt - architecture for Remote Operation Centers (or Integrated Planning Centers) - including two buildings I go past on a regular basis and never fully realised what goes on inside - the City of Stirling building, and the ECU Joondalup library.
Mike Lomman, OpX Solutions - planning considering bottlenecks
Andrew Jessett, MineWare - realtime dragline and shovel monitoring and support/maintenance orientated ROC's.
David Hattrick, Oracle Corporation - Oracles approach to managing mining data and information
Richard Taylor, Concept AV - Video walls

I put the Rocklogic animation up on youtube, it's pretty neat. Gives a short overview of the systems features - Remote operation, collision avoidance, automated movements (auto-park, auto-deploy), etc.

PDF tools

2011-11-23T21:24:00.002+08:00

PDF files are the standard document distribution format. PDF has long left other file formats in the dust. However, there are always a number of operations that people like to make to PDF's ranging from just creating them, to splitting or merging to applying a watermark or foreground stamp.

There are a number of great free tools to do all this work.

PDF Creator lets you create PDF files in Windows. Another popular alternative is CutePDF. For Apple Mac, under OSX you can simply print straight to PDF.

Splitting/bursting and merging/combining PDFs I feel is best done with a dedicated tool, PDFSAM - Split and Merge. Under OSX, you can actually use the sidebar of preview to move pages around, and drag in PDFs to merge, or pages to remove. If you have a lot of pages to do PDFSAM is a wiser choice, otherwise for smaller tasks Preview is fine.

Compression of PDFs under OSX is also straight forward, you just need to open the PDF in preview, and then under Quartz filter choose "Reduce File Size". Under windows, you can use PDFTK, more on this later.

Annotation of PDFs, again with OSX, preview gives you a small set of annotation tools. Under windows, you can use PDFTK. (Low cost / free for some-things aternatives are PDF-Xchange viewer and Foxit Reader)

Watermarking and Stamps are best done with PDFTK.

Encryption can be done with PDFTK, and under OSX, preview has an encrypt option.

Of course for those with cash, Adobe's tools are the best choice, but pdftk is a fantastic free alternative, if you don't mind a bit of command line typing.

An example of putting a foreground stamp onto every PDF with pdftk:

Generate a PDF where you would like to apply the stamp to (i.e. the source)
Create a stamp PDF. This should have the stamp you wish to apply (e.g. "DRAFT") and be a transparent PDF. Microsoft Word will generate transparent PDFs by default, so you can create your stamp in Word.
Apply the stamp to the source PDF using pdftk, for example:
```
pdftk in.pdf stamp stamp.pdf output out.pdf
```

Enjoy!

Robotics competitions and courses

2011-09-25T13:02:00.000+08:00

Sounds like it is competition season again.

UAV outback challenge where an unmanned ariel vehicle needs to find a person and drop supplies off to them. Registrations are due on the 27th September!
NASA Sample Return Centennial Challenge, a 1.5 million dollar prize competition to have robots autonomously explore a region, collect samples, and bring them back to base. Registration due in January, with the competition set for June. Only 8 months before the deadline when they announced the competition details - what are they thinking?
The ICRA solutions in perception challenge (May 2012), this doesn't seem too difficult - Identify and classify a set of objects, where you are given some training data/time. Use any sensor(s) you like.
Australian CiSRA ExtremeImaging competition an interesting computer-photography competition, due October this year, finals in November.

Many more are listed at the robot contests and competitions FAQ. To get you up to speed with robotics, there are some great free courses being run. The stanford Machine Learning course and the Introduction to AI class are both free to register, and start now! The ESA summer of code in space already started last month, but it is worth keeping an eye on for next time.

Civilization 5 - Casual/fast game mod for Apple Mac OSX

2011-09-12T22:17:00.000+08:00

I rarely have enough spare time these days to be able to play a game, let alone identify a block of time large enough to dedicate to a game like Civilization 5 - which can take up to 12 hours to play a fast game. So I decided to create a mod for Civ 5 that would significantly speed up gameplay and enable a game to be completed in a few hours.

Modding the game isn't directly supported under OSX, however it can be done.

First, edit MainMenu.lua, located in:

~/Library/Application Support/Steam/SteamApps/common/sid meier's civilization v/Assets/UI/FrontEnd

Comment the following line: (add a '--' to the start)

Controls.ModsButton:SetHide( true );

Copy a mod you have downloaded into the:

~/Documents/Aspyr/Sid Meier's Civilization 5/MODS

directory.

You will need to unzip/extract them before they will work.
If it is a civ5mod file, simply rename it to .7z, and you can use StuffitExpander or any similar tool to extract the folder.

Start Civ5, and you should see a 'MOD' option on the menu.

Creating your own mods is easy enough if you know how. Armed with a decent text editor and the console you can create mods under OSX. Begin by reading Dale's explanation of modinfo files. Next, the 2K games Civilization 5 wiki is a good place to visit, in particular the Civ 5 XML reference guide. Finally, the civfanatics modders guide provides an excellent overview of creating a mod.

You can use the command line 'md5' program to generate the MD5 hashes required for the modinfo file. (And online lower-to-uppercase conversion)

You can download my simple casual gaming mod for Civilization 5 here. It replaces the standard 'quick' game. At the beginning of the game, you will find most things only take one turn to complete. Things will start to settle down quickly though in classical times.

Eureka Prize for WAMbot

2011-09-06T21:51:00.015+08:00

The Australian WAMbot robot was selected as a finalist to the Eureka prize (Australia's top science prize) in the defence category. The awards ceremony took place in Sydney, at the Hordern Pavilion.

It was an interesting event, showcasing the best of Australian science. Stiff competition meant the first place in the Defence category was snatched away by Prof Abdesselam Bouzerdoum who has done fantastic work in novel sensing systems.

Maybe next time.

AIMEX

2011-09-06T21:06:00.000+08:00

I visited the Asia-Pacific International Mining Exhibition (AIMEX), held every four years. There was a lot of interesting technology on display, with a strong presence of simulators, drills and long-wall gear. Being mining, a lot of very large machines were on display, and the exhibition hall was huge. Automation also had a small presence.

Atlas-Copco had a set of their autonomous drill rig simulators on display, and I managed to get a chance to go through the process. Drilling is a non-trivial task, and it takes at least two weeks for an operator to familiarize themselves with the process. The autonomous drill system certainly makes it easier to operate the equipment, but the drill holes still have to be lined up manually - arguably the most challenging task.

Atlas Copco Autonomous Drill console

Eickhoff had a demonstration of their automated long-wall system, that uses the Indurad radar system.

CAT were displaying some of their new autonomous equipment, soon to be installed in
Western Australia at FMG's Solomon mine. CAT is always a slow mover to adopt technology but it is interesting to see how fast this technology is being adopted by the major Australian miners, now including Rio Tinto, BHP, Newcrest and FMG.

Eickhoff longwall automation

Below is a video of the CAT system I captured at AIMEX. Apparently this system actually does realtime path planning and adjustment as opposed to following a pre-programmed path like other (Sandvik) systems.

You can watch some more videos of autonomous mine vehicles on youtube:

Mozilla Demopart - The Self Explanatory Demo

2011-09-04T20:13:00.000+08:00

The Self-Explanatory Demo

With the help of Chris Mylrae (music) I put together a last minute entry to the Mozilla Demoparty demo competition. You can see our entry The Self Explanatory Demo. It derives and explains a number of oldschool demoscene effects, including the XOR bitplasma, sin/cos plasma, ripples, inteference, and tunnel effect. It also shows the origin of equations for radius of a circle, sine and cosine, tan and arctan, and 3d projection. In essence, it is an animated version of the demo effect explanations on this blog.

Overall, the demo placed in third place in the html5 WebGL demo competition. The winning single-effect entry WebGL water is well worth a look.

To put together my entry in the two days I had I used, three.js.
There is now a new tutorial site for three.js, it is definitely worth taking a look at.

Finally, I'll leave you with an amazing 64k production, 'uncovering static' by Fairlight and Alcatraz.

Kinect and OpenKinect on Apple Mac OSX

2011-08-16T21:51:00.001+08:00

Adrian, in Kinect-3D!

The Kinect is a revolutionary sensor for robotics - the low price point has seen an explosion of interest and applications in this field. (Hopefully we will see the same for the Neato XV11 low cost laser scanner one day). I was very impressed by the data the Kinect returned, it is a fantastic device.

To get started, just follow the OSX install instructions at OpenKinect. You will need MacPorts. A copy of the instructions is here:

sudo port install git-core

sudo port install libtool

sudo port install libusb-devel

git clone https://github.com/OpenKinect/libfreenect.git

cd libfreenect

mkdir build

cd build

ccmake ..

cmake ..

make

sudo make install

(Press 'g' to generate your cmake make files). Very simple.

Now check under system profiler to see that the Kinect device is detected.

I had the following error when I tried to read from the device:

Isochronous transfer error: 1

Thankfully, this was easy to solve with a fully self-contained installer from AS3 kinect OSX download package. You should now be able to read the color image, depth map, and command the servo.

The next step will likely be to interpret the data in some form. The Point Cloud Library will be very useful for processing the data. A tutorial on Point Cloud Library is available, although many features are breezed over.

But to begin with PCL, you will need Eigen, a fast vector and matrix math library. (Also used in MRPT)
First download Eigen, and unzip it. Building Eigen is quite straight forward:

cd eigen-eigen-3.0.1

mkdir build

cd build/

cmake ../

sudo make install

PCL has a self installing package, and will install itself to /usr/local/lib/libpcl_*
Here is a simple test program from the tutorial:

#include

#include "pcl/io/pcd_io.h"

#include "pcl/point_types.h"

int main (int argc, char** argv) {

pcl::PointCloud cloud;

//Fill the cloud data

cloud.width = 5;

cloud.height = 1;

cloud.is_dense = false;

cloud.points.resize(cloud.width * cloud.height);

for (size_t i = 0; i < cloud.points.size(); ++i) {

cloud.points[i].x = 1024 * rand() / (RAND_MAX + 1.0);

cloud.points[i].y = 1024 * rand() / (RAND_MAX + 1.0);

cloud.points[i].z = 1024 * rand() / (RAND_MAX + 1.0);

}

pcl::io::savePCDFileASCII("test_pcd.pcd", cloud);

std::cerr << "Saved " << cloud.points.size () << " data points to test_pcd.pcd. " << std::endl;

for (size_t i = 0; i < cloud.points.size(); ++i)

std::cerr << " " << cloud.points[i].x << " " << cloud.points[i].y << " " << cloud.points[i].z << std::endl;

return(0);

}

This can be compiled directly with:

g++ pcd_write.cpp -c -I /usr/local/include/pcl-1.0/ -I /usr/local/include/eigen3/ 

g++ pcd_write.o /usr/local/lib/libpcl_io.dylib

Finally, attached is a youtube video showing some very impressive visual SLAM surface reconstruction with the Kinect (See KinectFusion project page).

Of course, you will probably want some image stabilization technology to get smooth input videos, so why not try an Owl?

Happy Hacking!

ROS - Robot Operating System

2011-08-12T13:45:00.000+08:00

Not so long ago there were a number of robotics packages that provided a variety of functionality of various tasks, such as OpenCV for computer vision, MRPT for mobile robots and ORCOS for general functions. Recently, this has changed as Robot Operating System (ROS) has become the predominant system which has swallowed the functionality of all the other packages.

ROS functionality includes:

Support for various sensors and robots including Neato XV-11, Roomba, IRobot, Pioneer/ARIA, Nao, Android, KUKA, Sick, Hokuyo, Bumblebee, Firewire cameras, Webcameras, Xsens, Wiimote, EtherCAT, CAN
Support for a number of other libraries/packages including CUDA, OpenCV, Eigen, PCL, SVM/Bayesian, Spatial subdivision, OGRE, XML, and many more.
Motion planning library for mobile robots
3d Navigation stack
Inverse dynamics for robotic manipulators with calibration points
SLAM packages including Graph SLAM (see Laser SLAM), RGBD 6D SLAM and Spares visual SLAM (also ScaViSLAM)
Multi target tracking
People detection with laser (leg) and vision
Physics engines including ODE and Bullet, and the Gazebo and OpenRAVE simulators and COLLADA loaders.
ROS functionality overview at the CoTeSys ROS school held at the Technical University Munich (my old visiting University).

Refer to this full list of ROS packages. The functionality encapsulated by ROS is both amazing and disturbing.

I've never been a fan of massive (disorganised!) frameworks that force a work structure onto you, but the robotics world isn't leaving you with much choice anymore. After implementing a graph based information flow architecture in ImprovCV and working closely with DirectShow's graphfilter I'm also keenly aware of the limitations of a graph-based approach to software development. It's not a one-size-fits-all solution, unfortunately ROS leaves little choice.

Thankfully some ROS packages are largely stand alone, so there is still some hope that one day some organisation will put in the effort to streamline and clean up ROS overall.

In any case getting ROS running on Apple Mac OSX 10.6 was not too difficult, however I lost my install notes in an untimely crash, so I'll only give a brief overview. ROS installation relies on MacPorts. I'd been holding off on installing MacPorts as it has historically been unstable, and doesn't play nicely with already installed libraries. MacPorts is now stable and well tested, but it still doesn't play nice with the rest of your system.

To install ROS I followed the ROS diamondback OSX installation instructions, all without any major dramas. I did have to alter the CMakeLists.txt as suggested in the troubleshooting section.

MacPorts gave me a few headaches, some of the errors I encountered were:

Error: Target org.macports.install returned: no destroot found

To solve, use:
```
sudo port clean NAME
```
Error: NAME already exists and does not belong to a registered port

To solve, use:
```
sudo port -f activate NAME
```

Once ROS is all installed you can source setup.sh. Remember to add in any additional packages to ROS_PACKAGE_PATH.

All in all, I wouldn't recommend running ROS on OSX, although the base ROS install works without any major dramas, installing each individual package is a bit of a struggle.

I believe ROS is an appropriate name, it really should be a stand alone operating system. I would strongly advise setting up a separate linux OS dedicated to your ROS install, running ROS ontop of OSX is quite problematic.

Communications and Messaging Frameworks

2011-08-10T19:58:00.001+08:00

A common problem for any distributed software project is handling inter process communications and messaging. Luckily, a number of frameworks already exist to solve this issue. Robotics projects tend to have a range of requirements, from providing a higher level cognitive architecture framework (typically a set of interacting components or nodes) to low-level realtime communications (e.g. CANbus, RT ethernet).

Some robotics packages already provide a particular architecture, such as ImprovCV and ROS which are both filter based, or MRPT which provides some IPC primitives. However, this problem is hardly limited to robotics and many real time distributed networking/processing systems have similar communications requirements. (e.g. computer games, or traffic management systems / plant control systems).

The communications frameworks can be broadly grouped into three categories:

Integrated middlewear for a larger package
(hard) Real time control orientated frameworks
(soft) Real time messaging libraries

From a games perspective, the people at second life have a nice evaluation of several messaging systems. Beginning with soft real time messaging, some interesting libraries include:

Google protocol buffers, for serialisation. I mention it, because it is popular.
MessagePack is a language agnostic message serialisation system similar to Google protocol buffers - just faster and better.
CORBA allows objects to be sent around a network, often used in business applications. It is an open standard and language agnostic as it includes an Interface Definition Language to define components.
Microsoft DCOM / .NET remote and its many variants are similar to CORBA, just the Microsoft variant.
Apache ActiveMQ another enterprise orientated message broker with support for a large number of scripting languages (Python, PHP, Ruby, Perl, etc).
RakNet manages distributed objects, primarily targeted towards computer games (used in Unity).

Open Torque Networking Library has its origins in the Torque game engine designed for massively multiplayer games.

YAMI4 is a fairly advanced but easy to use peer to peer messaging framework for control systems that is easy to extend to a pub/sub system. POSIX, Windows, Java, C++, well worth a look.

0MQ, zero MQ is a messaging system that is socket based, and also has pub/sub extensions.

Socket.IO hardly qualifies for a framework, but is a great enabler for realtime HTML communications, so it certainly deserves a mention.

there are many more networking libraries available, but these are the ones that stand out for this category. For hard real-time control tasks the choices are a bit more limited, however libraries of note are:

Real time CORBA, is CORBA modified to be a bit more lightweight and able to support real time requirements. TAO ACE is worth looking into if your following this path.
Data Distribution Service (DDS) is similar to Real time CORBA, however it has the advantage of lessons learnt from CORBA and provides simpler fine grained control over quality of service and intelligent networking. RTI DDS is the framework we used for the WAMbot TARDEC/DSTO MAGIC 2010 project. OpenDDS is an open source implementation.
Real time data base (RTDB) is an open source framework that provides a lower-level communications interface for C/C++ over Xenomai. This is the framework we used for the Team Annieway entry to the DARPA Urban Challenge.
LCM is a socket-based IPC library used by Team Michigan for MAGIC 2010.
IPC a low level inter process communications system for embedded systems used by NASA.
Dynamic Data eXchange (DDX) is a large open source distributed software architecture developed by CSIRO and has been previously integrated with ROS.

Finally, there are a number of application specific frameworks, for Robotics this includes ROS, MS Robot Studio, Player/Stage, JAUS and more general packages such as Labview and Matlab. I think it is prudent for every software developer to be familiar with at least three tiers of communications frameworks, from large scale frameworks (e.g. CORBA) to light-weight frameworks (e.g. RackNet) to low-level frameworks (e.g. Socket.IO). Ideally, one for each key application area (e.g. Hard real time, Soft real time, Business applications, Web).

Half year catchup on Graphics, GPUs, Compilers, etc.

2011-07-29T13:13:00.000+08:00

Another slow month on the blog. More than half way through the year, so its time to catch up on the backlog of news. Only covering graphics, games, physics and GPGPU and compilers. Expect a number of posts on robotics soon!

GitHub is now more popular than SourceForge.
Fabian 'ryg' Giesen has put together an in-depth explanation of the graphics hardware pipeline.
nVidia released an extension to allow OpenGL direct access to DirectX buffers. Now you can write your graphics programs in both OpenGL and DirectX - pick whichever is easiest.
nVidia released their 11th Graphics SDK - DirectX 11 only.
Aras did a blog post on visualising mip-map levels and released the code to his shader.
Redirect OpenGL from a remote machine with this VirtualGL tutorial.
Morphological Anti-Aliasing paper with source code.
Tim Lottes released his FXAA anti-aliasing source code
José María Méndez wrote a fantastic article on a simple method to implement screen space ambient occlusion.
Improve your ambient occlusion with occlusion normals to enable dynamic shading.
A simple GLSLShader handling class
Dave has a post on how you can generate game characters with a webcam.
Source code from the Game Development Tools book. From texture generation and CSG to Continuous Integration, Perforce and XML.
Steven Wittens has a fantastic series of posts on procedurally generating planets and worlds.
Amit's blog post on polygon map generation using Voroni and Delaunay is worth a read.
The old gameUltima 6 technical documents have been released. An interesting look at game design and programming decisions made in 1990. This should help nuvie, which has already made great progress.
Oldskool demoscener Trixter wrote an interesting post onC64 vs IBM PC, and argues the C64 was a faster computer.
Democoder Ferris/YUP did an interesting post on
creating a tiny 1k graphics demo.
John Ratcliff updated his Hierarchical Approximate Convex Decomposition utility library.
Tim Ventimiglia and Kevin Wayne did an interesting post onusing the Barnes-Hut algorithm to accelerate n-body simulations.
Pierre Terdiman has a great post on fast separating axis tests to speed up your collision detection for convex objects.
PhysBAM source code - there is plenty of great stuff in here, so I'm sure to do a whole blog post on this later. It covers maths (e.g. ODEs, fourier transforms), spatial subdivision (KD trees, octrees), collision detection, raytracing and so much more.
OpenCloth is a new library for cloth simulation algorithms.
nVidia APEX SDK is now free. It has a number of functions that help with clothing and destruction physics.
PhysxLab is a digital content creation tool to help you take advantage of the APEX sdk destruction features.
The Oren Game Engine blog has a great post onimplementing destruction fractures.
A realtime raytracer with pure C++, OpenMP and CUDA written by Thanassis Tsiodras is accompanied by some interesting analysis.
Microsoft Accelerated Massive Parallelism (C++ AMP) appears to be the microsoft attempt at competing with CUDA, OpenCL and some of the libraries ontop of those technologies.
Microsoft also released concurrent containers, parallel versions of STL algorithms.
WebCL - OpenCL for the web, at Nokia research.
AMD's OpenCL University kit covers some OpenCL and GPU basics.
AMD Accelerated Parallel Processing (APP) SDK (formerly ATI Stream) has had a few updates, currently 2.4 is out.
AMD gDEBugger is now free for debugging OpenGL and OpenCL programs.
Intel SPMD Program Compiler is designed to generate optimal SIMD programs from a C-like language.
PathScale EKOPath 4 is an optimising compiler, now free for linux, BSD and Solaris.
Yang Chen wrote an amazing post comparing compiler optimizations.
Helpful hints on the unix command xargs
FreeArc is an amazing open source compressor. Fast and fantastic compression ratios.
Google's excellent diff/match/patch tools
Visual hashing explained, how to detect similar images.
Ocropus is a open source library for Optical Character Recognition (OCR).

Finally, here is the SIGGRAPH 2011 technical papers highlights video, it contains a number of interesting advances in physics simulations and modeling.

CAD on OSX with Blender and Rhino - DWG

2011-06-27T13:14:00.004+08:00

The majority of the engineering world use AutoCAD-like products for creating drawings, with typical exchange formats of DWG, DXF, SAT or IGES. (I wrote some tips on using AutoCAD and SolidEdge here) Unfortunately on OSX there has been historically little choice. I asked Stefan Boeykens who runs the CAD 3D blog for suggestions, and compiled a list of possibilities:

AutoCAD have a Mac OSX version. Obviously 100% DWG support, the downside is the price (Retails for $3,995, 30 day trial)
iCADmac is a mac port of progeCAD, that is actually very good on OSX (still a poorer cousin of AutoCAD). I use this for 2D CAD work on OSX. (Retails ~$1000, 30 day trial)
ARES commander is a cross platform CAD package for Windows,OSX,Linux. So there should be no compatibility issues between. I've not tried it out myself. (Retails $795, 30 day trial)
Blender is a free cross platform 3D package, that does have DWG/DXF plugin support. Unfortunately, the DWG support is not very good, and it is difficult to get the plugin to work under OSX and Linux. (free, Open Source)
Rhino 3D, a free trial version for OSX at the moment. (Retail expected ~$1000, free unrestricted trial while in beta)

Although Stefan mentioned some issues with Rhino3D, it worked perfectly with all my CAD files, and it is still an alpha product at the moment. Rhino3D supports a lot of file formats to a high standard:

3dm (Rhino format)
3ds (3d Studio, original not Max)
dwg (AutoCAD - I tested the 2007 version)
dxf (AutoCAD)
fbx (MotionBuilder)
iges (IGES)
lwo (Lightwave)
obj (Wavefront)
sat (ACIS) [Export only]
stl (Stereolithography)
vrml (VRML, also wrl file format)

In the end, I only used Rhino3D to convert the data and used Blender for doing most of my data manipulation, as I already have a number of scripts for it (See Convex hull generation for Blender). Every time I get back to using Blender after a pause it takes me a while to get used to the interface, here are some common commands I use when manipulating objects to conform to a given coordinate system:

space - add an object
g - move (follow by x,y,z to select an axis)
r - rotate (follow by x,y,z to select an axis)
a - selects all objects
h - hide objects
. - zooms so you can see all
0 - switches to camera view (F9 - edit panel, you can set the FOV by altering 'D')
n - displays the current transformation matrix (To find the global coordinates you should view the Object in edit mode)
SHIFT+c - centres the cursor
View->View properties - allows you to manually enter the cursor position
Object->Transform->Center Cursor - allows you to re-define the center of the object
CTRL+a - collapses the rotation/scale transformation matrices. (see above for setting the position)
CTRL+p - to parent objects, allowing you to move them in groups

This Blender keyboard shortcut map always comes in handy too!

Deform (textured interference) effect in WebGL

2011-06-17T22:48:00.003+08:00

'deform' interference effect

This effect is one of my all time favourites. It is somewhat similar to the XOR bitplasma effect with which I started the tutorial series based on iq's shader toy. This effect is an 'interference' of two points based on the subtraction of the radii and angles.

Jumping straight to the solution; the code we are trying to decipher is:


float a1 = atan(p.y-offset1.y,p.x-offset1.x);
float r1 = sqrt(dot(p-offset1,p-offset1));
float a2 = atan(p.y-offset2.y,p.x-offset2.x);
float r2 = sqrt(dot(p-offset2,p-offset2));

vec2 uv;
uv.x =(r1-r2);
uv.y =(a1-a2);

So why does it look the way it looks?

Lets start with the radius part. If we just look at one radius (r1) we would expect to see a steadily increasing value radiating out from our offset point (in all my examples this will be at 0.3)

And this is exactly what we see when we plot this. If we plot the inverse (negative r2, offset to -0.3) we should see the inverse, that is, a steadily decreasing value radiating from the offset point.

r1-r2

So if we combine these (r1-r2) we get a nice smooth surface transition between these two patterns. Where does this blending come from?

Lets take it back a step and look at our problem in just one dimension. Our definition of the radius is sqrt(x*x+y*y), in 1D we can plot x*x and sqrt(x*x):

Coming back to the generation of the surface, we can plot two interfering 1D functions, that is sqrt((x-0.3)*(x-0.3)) and sqrt((x+0.3)*(x+0.3)), and the difference (i.e. the first subtract the second). This gives us a ramped step between the functions as each reaches its turning point.

We can see the same feature in the surface, if we view it from an appropriate angle.

r1-r2, alternative view

We still haven't discovered the cause of the smooth blending that gives such a nice visual effect. When we add a constant (i.e. offset) to the function sqrt(x*x+k), notice how we now have the turning point at sqrt(k) and have a parabola instead. This is effectively evaluating sqrt(x*x+y*y) for some constant y=sqrt(k).

So, if we now consider the two extremes, again plotting in 1D but considering the 2D case for both our x-offsets of =-0.3 and 0.3 we get a set of blended curves (dark blue/red is y=-0.3, light blue/purple is y = 0.3).

And that is where our full surface comes from.

Left: atan(x) Right: atan(1/y)

Now we want to understand the blend in the angles. The generating function is nothing more complex than atan(x/y). Below is a graph of atan(x), followed by atan(1/y). Note: There are different viewing angles for each function so it is easier to see the curvature.

If we combine these two equations into one (i.e. atan(x/y)) we get:

atan(x/y)

Now, we just need to understand the interference pattern that is generated from two of these functions interacting. I'm going to take a shortcut here and just let an animated gif tell the story. This animation shows a discretized version of the angles (first in steps of ~60 degrees, then ~30, etc.) interacting for the equation a1-a2 from the code snippet.

a1-a2 discretized and animated (open as a separate image)

From the gif you can see how the curves evolve. To understand these better we can take a look at how this curve pattern comes about for a constant difference angle. If we modify the end of our original shader code to:


uv.y = (a2-a1);
float k = 0.0;
if ((uv.y > 0.3) && (uv.y<0.31)) k = 1.0; gl_FragColor = vec4(col.r+k,col.g+k,col.b+k,1.0);

The resulting image is still the original effect, but one of the curves is highlighted (in white). This represents a curve where (a2-a1) ~= 0.3

We can understand this curve by generating a set of triangles in which two vertices are fixed, and the difference between two angles is held constant. By altering one angle the final vertex will generate the sweeping curve in the original image (See Law of Sines). In the example below, we vary a1 and hold a2 as (a1 - 30 degrees).

This generates our final explanatory image of the sweeping triangles:

Finally! The full effect has been deciphered, click the button below to see it in action. (You will need a WebGL enabled browser)

Demoparties

2011-06-13T23:08:00.002+08:00

Australia is hosting another demo party, this time in Sydney called Flashback 2011. It will be interesting to see what gets released.

For a more international focus there is the Mozilla Demoparty with WebGL, CSS, GIF animation, and Audio competitions. The 'event' started on the 10th of June, and submissions close on the 30th of July. Take a look at the original announcement of the Mozilla Demoparty incase you want to organize a local contributing event.

If your looking for a modern tracker to make your audio you can try the open source Schism Tracker (Impulse Tracker clone). (Daniel Gagan has a nice blog post on various methods for implementing HTML5 audio loops) For your WebGL needs, there are a number of libraries/engines to try:

CopperLicht a port of the Irrlicht 3D engine to WebGL
X3D via WebGL an easy way to display 3D models
GLGE a WebGL javascript library with some basic 3D engine functions (Keyframe animation, Lighting & Materials, etc)
three.js a lightweight 3d Javascript engine
o3d WebGL port, from google.
JAX framework.

Should be enough to get you started. Of related interest is a description of Brandan Jones' WebGL renderer for id's Rage levels.

Catchup Post: Robotics and Physical Simulations

2011-06-05T18:27:00.000+08:00

A number of robotics related bits of interest from the last few months:

Articulated Swimming Creatures by Jie Tan et. al actually performed work I had planned for my thesis, but never did complete. They simulated various creatures using different fluid simulation methods, and found they get different results. This was the same thing I found, and generalised via PAL and used to generate control algorithms that can transfer to the real world for an underwater vehicle.
Predator: A Visual Tracker that Learns from its Errors by Zdenek Kalal went viral. I think it was a bit hyped (thanks to a clever name), but the TLD algorithm is interesting, and there are some worthwhile items to note. First of all it is an open source visual tracker, and that there is a freely available
Google Tech Talk on TLD. In essence, Zdenek asserts that a tracker based on similarity of image patches will always lose its target and demonstrates trackers with learnt models from image data perform very well. (Similar to how models improve tracking in OpenTL). Zdenek et al. describe a way to generate more test sets using two experts (positive - objects must remain nearby, negative - only one true location per frame) and leverages boosting to get results. The total flow of operations are then: 1. Tracking and prediction, 2. Expert systems plus Detection, into Learning. 3. Re-Detection, using learnings.
Paul Firth published a great introductory article on Physics Engines. Very handy. While your at it, Wolfgang Engel did a great post on some maths basics.
Hierarchical Approximate Convex Decomposition of 3D Meshes (HACD) (HACD paper) is a method for representing objects as compound convex hulls (speeds up collision detection), that seems to outperform any other method I have seen.
C2A by Min Tang et. al is a method for speeding up continuous collision detection with conservative advancement. A good paper, and source code is available.
PAPPE is a Pascal Physics Engine.
Barbara Solenthaler and Markus Gross published work on Two-Scale SPH Particle Simulation, an obvious idea (speedup simulations by mixing level of detail for SPH, they get about 2.2x speedups), someone had to do it. The videos are interesting nevertheless.
On the topic of SPH, PhysXinfo has an article on the latests nVidia PhysX/Novodex/ETH research on fluid systems, of particular interest is Solid Simulation with Oriented Particles. Another interesting post is by Miles Macklin on fluid simulations.
Intel released 'Colony' a crowd-simulation system, comes with source code.
Lectures on machine learning with Matlab. Covers SVM, NN, EM, Bayesian methods, and image analysis.
Ant colony optimization will be the next google AI challenge.
An XML Unified Robot Description Format (URDF), again, like many other formats before it it has inherit limitations. COLLADA 1.5 Kinematics (library_kinematics_models) is probably a better choice.
On the topic of XML, and other data interchange formats JSON cpp is a C++ library to handle exchanging JSON data.
ACRA, the Australasian Conference on Robotics and Automation will take place in December in Melbourne.
And just incase you've been hiding under a rock for the last while, the next big DARPA competition is the ARM manipulation program. Lots of interesting results are coming out of that project, but thats for another time.

Finally Heat-1 the space rocket build by danish amateurs Copenhagen Suborbitals successfully launched. (TED talk here). See the video below.

Slides on the Demoscene and WebGL demo effects

2011-05-16T21:41:00.003+08:00

I gave a guest lecture at ECU for the Advanced 3D Graphics programming class. The slides cover:

A bit about me
An introduction to the Demoscene
An introduction to WebGL
WebGL Shaders
Screen space
Sine/Cosine Plasma effect
Circle equation and XOR Bitplasma effect
Tangent function, 3d to 2d projection, Texture mapping and Tunnel effect
Twist effect
Julia fractal

You can get the slides on WebGL and the Demoscene here. Enjoy!

China Holiday

2011-05-09T21:18:00.040+08:00

Yangshuo

I have been holidaying in china, which explains the lack of posts on the blog.

I went to China as a relatively experienced independent traveler with a western-cultural-view of China. A few things stood out to me as being quite different to the current prevailing western perception of China:

China isn't one unified country. China is only slightly smaller than the US, and 1.24x the size of Australia - plenty of room for variance. There are regions of conflict (e.g. Tibet, Xinjiang Uighur, etc.) and there is a massive diversity in the people, cultures, and languages. 'One country, two systems' (e.g. Hong Kong) gives a bit of an indication of the diversity within China. I'm not sure there is another country with this range of diversity.

Shangri-La

There are plenty of rich people in China (According to some (dubious) sources, there are more billionaires in China than the US. In any case, there are plenty of Starbucks, McDonalds and KFC restaurants!). Especially in cities like Beijing and Shanghai. China's GDP and PPP have increased significantly in recent years, and in urban areas people are much better off than the western perception which is based on historical figures. There are obviously still a great number of poor people too.
I found the level of censorship is not as great as western sources report. It seems to be a 'work in progress', but people appear to have a fair amount of freedom of expression (compared to the perception presented by western media on communist nations). There were people on Chinese TV openly complaining about government corruption, housing problems, etc.

Temple of Heaven

Some travel tips for an independent traveler:

China changes rapidly. Take an up to date travel guide.
Booking flights, accommodation, etc. can be quite difficult. Ctrip is a very helpful website.
Take a print out of your accommodations address in mandarin, phone number, and a map. This will increase the probability of you arriving at your destination.
Avoid getting scammed with travel bookings by asking any decent hotel to help in booking anything from tours to transport to taxis. You will always pay a surcharge, but never get ripped off.
There can be a large cultural barrier. I've traveled to countries with significant language barriers, but have always been able to explain myself via gestures and drawing pictures. I guess the cultural barrier made it difficult to explain myself!
When asking for directions ask multiple people. Often someone who doesn't know will just make something up.

Great Wall

Be careful when haggling, often the "pay half" rule doesn't apply, and "pay 1/10th" is more appropriate.
There is a lot of internal tourism in China. Don't expect to see many foreigners. Expect to draw a fair bit of attention from the locals.
Take a print-out of a few key phrases in mandarin. I found this particularly helpful in deciphering menus and ordering food.

Highlights for me were the Temple of heaven and Summer palace in Beijing, the Putuo Zongcheng Temple in Chengde, the Great Wall surroundings, Shangri La, Hong Kong and Yangshuo.

Expect a return to technical topics soon!

March update

2011-03-31T23:55:00.000+08:00

I didn't want to have a month without a post, so here are some links for the month:

GDC 2011 is over again. I'll do a breakdown soon, but meanwhile take a look yourself at DICE publications on Battlefield 3, nVidia's GDC publications, AMD GDC and ofcourse the official GDC vault (free). (Maciej Sinilo has a nice collection here).
Game Physics Pearls has been published by Gino van den Bergen and Dirk Gregorius. Dirk is a very knowledgeable guy, and Gino wrote SOLID, so I'm sure it's great.
ScienceBooksOnline has a collection of free books.
Paul Firth has a great interactive blog post on contact resolution, and introduces a method used in Little Big Planet he calls "Speculative Contacts".
PhysX info has a comparison of different clothing simulation systems.
GLM is an OpenGL syntax math library.
Cairo is a 2D graphics library that supports both OpenGL and PDF output.
An MIT WebGL tutorial.
How to convert your HTML5 page into a native OSX app.
Paul Grenfell added another small raycasting OpenProcessing demo.
Photoshop filters implemented in GLSL
Herwig Hauser has an amazing gallery of 3D algebraic surfaces - useful for 4k productions.
On that topic, Auld has a great snippet on miniature GLSL code for moving a camera.
0 AD is an open source 'Age of Empires' style game.
Ninite is like apt-get for Windows. (Installation package manager)
A siggraph paper on the miniature effect
Bundler is an open source tool to generate structure from motion from unordered images. (It was published in 2006, but now you can look at the code)
GPU Ocelot 2.0 supports AMD devices now. CUDA for AMD.
Microsoft's paper on the Kinect bodypart tracking algorithm.
Looking for a place to publish? Wiki Call for Papers collects conference paper submission deadlines and more. (Neat!)

The pick of the month has to be the new Festo production, the SmartBird ornithopter. (Official site has a PDF spec-sheet). Video below:

WAMBot on ABC Catalyst

2011-02-24T23:50:00.000+08:00

ABC Catalyst did a segment on the MAGIC 2010 competition, you can watch the Catalyst RobotWars MAGIC2010 segment on their website.

A more in-depth explanation of the problems we faced: The robots were stored overnight on site in a tent, and unfortunately the next day a lot of moisture had gathered in the electronics. Since we had used cheap GPS units, a number of them then failed on the day. The software we had written was not robust enough to cope with the faulty units and so the robots would think they were in an incorrect location. As the fleet of robots could not agree on their locations the map data was incomplete, and subsequently the robots were difficult to navigate.

Other software bugs, short battery life and communications drops also hindered the performance.

Next time: More testing, and focus on robustness and fallback options, and buy equipment with an IP rating of 32 or more.

A short clip of the interview is on youtube:

Newton Physics Engine

2011-02-20T21:07:00.000+08:00

In an unexpected move the Newton Physics Engine has been open sourced with the zlib licence. I haven't been following this engines developments closely since the 1.x versions. Julio has released the 3.0 version over svn as well.

Finally, a chance to figure out some of Newton's strange behaviour I noticed in the PAL physics engine benchmarks.

Sphere effect in WebGL

2011-02-12T20:19:00.001+08:00

This effect is quit interesting to decompose. There are a few versions out there with some confusing formulations and constants, however in essence they all come from the same principles. This version is based on one by Luis Gonzalez, which in turn was based Iñigo Quilez's version (formula 14). (iq emailed me to tell me about his windows-only program, but the data file is plain-text - lots more effects to decompose! Thanks iq!)

First, we start with our trusty radius calculation:


vec2 p = -1.0 + 2.0 * gl_FragCoord.xy / resolution.xy;
float r =sqrt(dot(p,p));

Now to generate a sphere-like looking object we want to create something that looks somewhat like a parabola when we take a slice of it. By careful choice of our equations we should be able to construct the appropriate curve. First, since we are creating a sphere we need to create the outline of the sphere, which of course will be a circle. We can use the fact that the square-root of a negative number will be 'undefined' (complex) to generate the outline of our sphere:

 float f = sqrt(1.0 - r*r);
gl_FragColor = vec4(f,0.0,0.0, 1.0);

Inside the 'sphere' (inverted below)

This generates a circle from a re-arrangment of the circle equation (simplified for unit circle):

x²+y²=1
y²=1-x²
y=sqrt(1-x²)

If you apply a linear texture to this, you will notice that it seems like we are looking at the 'inside' of a parabola, and to get something that looks like a sphere, we need to be looking from the 'outside'. We can fix this by inverting our previous result:

 vec2 p = -1.0 + 2.0 * gl_FragCoord.xy / resolution.xy;
vec2 uv;
float r =sqrt(dot(p,p));
float f = 1.0 - sqrt(1.0 - r*r);
uv.x = p.x*f;
uv.y = p.y*f;
gl_FragColor = vec4(texture2D(tex,uv).xyz, 1.0);

Gee, that looks vaguely sphereoid already. We just need to make it look more 3D. Well, lets try generating a sphere from the equation of a circle:

z=r*r

r = sqrt(x*x+y*y);
z = r*r;

Recall from the tunnel tutorial that to project from 3D to 2D we simply need to divide by z. We can use the 3D equation of the sphere to calculate the Z depth of the sphere, (i.e. divide by r*r).

Its starting to look good, now we just need to finish it off with a perspective divide and we have our final result (we can also factor out the redundant square-root):

 vec2 p = -1.0 + 2.0 * gl_FragCoord.xy / resolution.xy;
vec2 uv;
float r = dot(p,p);
float f = (1.0-sqrt(1.0-r))/(r);
uv.x = p.x*f + time;
uv.y = p.y*f + time;
gl_FragColor = vec4(texture2D(tex,uv).xyz, 1.0);

It's not raytracing, but it looks pretty good.

Ripple effect in WebGL

2011-02-07T23:46:00.000+08:00

There is really nothing special to the ripple effect, in essence it is just an evaluation of the sombrero function. This is just a 2D version of the sinc function.

Below is a graph of the sin function, followed by sinc.

Left: sin(x); Right: sin(x) / x

Extending this to 2D we have:

r = sqrt (x*x + y*y);
z = sin (r) / r;

Plotting this as (x,y,z) we have the sombrero function:

To turn it into a ripple-like looking effect we just need to scale down the "height" of the function, and animate it by adding time into the sin term to generate a repeating pulse. The complete GLSL code is:


#ifdef GL_ES
precision highp float;
#endif

uniform float time;
uniform vec2 resolution;
uniform sampler2D tex;

void main(void) {
vec2 cPos = -1.0 + 2.0 * gl_FragCoord.xy / resolution.xy;
float cLength = length(cPos);

vec2 uv = gl_FragCoord.xy/resolution.xy+(cPos/cLength)*cos(cLength*12.0-time*4.0)*0.03;
vec3 col = texture2D(tex,uv).xyz;

gl_FragColor = vec4(col,1.0);
}

Despaire by Iguana ported to Mac OSX

2011-02-06T22:30:00.000+08:00

One of my favourite old demos is Despair by Iguana. It features a number of nice effects including realtime raytracing, blended particles, and many more effects that were ahead of its time (It was released in 1996!). The source code for the demo was released and ported to 32bit by David 'mac' from ThreePixels. So I took it upon myself to port it from 32bit windows to 64bit OSX / *nix.

First I translated David's version to VS2010 and ported it to use SDL and the latest BASS, compiling it on windows, to ensure it was all running.
I stripped out all the non-portable assembly code. Unfortunately none of this code was commented, and the few comments that were in there, were all in spanish. (I think)
I installed Intel C++ Composer XE 2011 for Mac OS* X (The Intel C++ compiler on OSX), to keep the code compatible with VS as far as possible, and created a makefile.
I ported the code across to OSX. Nothing too special here, replacing a few windows and DOS function calls with their POSIX equivalents. This part of the port followed the same process as porting any other windows application to another platform. (I'd already done the port to SDL)
I requested (and received! Thanks Ian!) a 64bit copy of BASS for OSX.
Success! A stripped down version of Despair ran on OSX, very few effects actually worked. Now the fun (pain?) could begin.
I looked through all the assembly code and realised quickly that I would never be able to port it all. Instead, I figured I would take an educated guess at the functionality.
I noted some assembly code "RenderBandScan" and took a quick look and spotted a:
```
and eax,0F0F0F0F0h
```
Immediately, I recalled the old trick of using bitwise and and shifts to quickly sum 4 pixels at once, and re-implemented this in a simple C loop.
The next routine was "AADump", a little trickier this time, but again a well known pattern:
```
 mov cl,[esi+1]
 mov bl,[esi+320]
 add eax,ecx
 mov dl,[esi+321]
 add eax,ebx
 add ecx,edx
 add eax,edx
 mov dl,[esi+2]
 shr eax,2
```
The pattern of adds and a shift for quickly "blurring" an image, from that basis I just re-implemented a blur-copy routine, and all was well.
I came across the cryptic "DumpScanASM" routine. Luckily, there was a section of c-code commented out that I could just drop back in to replace this. Phew!
The next function was "RenderScan". The name was quite self-explanatory, however I noted a fair bit of odd '127' in there. Knowing the effect was alpha blending some blobs, I deduced the C code:
for (i=0;i127) sum = 127; dest[i]=sum; }
The second last effect that needed translation from assembly to C was "FB_Draw320x200". This was a bit cryptic, but essentially it was a fixed-point texture sampling routine with a number of clever bit-shifts. I didn't quite get this one converted correctly.
Finally, the greets section is a rotozoomer, texture mapping and blending routine written in pure assembly. This is where I call it a day. I'm not converting this beast! (If anyone else wants to you will need to re-code: DrawGrScan, and VSTM_DumpScan2000.. good luck!)

Here is a zip of the OSX executable for the Despair/Iguana demo along with the ported source code and make files.Youtube video below:

Ported Trip! (4k intro) to OSX

2011-02-02T22:03:00.000+08:00

There are very few products from the demoscene that are available on Mac OSX.

In preparation for some more challenging ports of old demoscene products across to OSX I thought I would start with one of my own productions. Unfortunately, I historically used DirectX, but I did do one OpenGL production, Trip! for Syntax 2007. And now, the Mac OSX (Intel) port of Trip! for Syntax 2007, unfortunately nowhere near 4k anymore. (Warning: Plenty of black/white flashes, the illusions will only work if you stare at the center of the screen)

Twist Effect in WebGL

2011-01-31T21:35:00.000+08:00

The twist/twirl effect is achieved with a combination of techniques I've already discussed:

Radius (r)

Combining these will give us a 'twisting' effect. Unfortunately, this is almost impossible to explain without pictures.

Unlike the previous examples where I used shaders to explain each component, it will be easier to explain this with some graphs. In the graph each color represents a different height, so from our circle-equation we get:
float r = sqrt(dot(p,p))/sqrt(2.0);

From the tangent-equation we get:
float a = atan(p.y,p.x) / (2.0*3.1416);

Angle (a)

Twisting is essentially a spiral, and we can generate a spiral by stepping out a constant amount towards the radius as we progress around a circle. For example, we start at 0 degrees, at 0% of a step away, then move to 45 degrees at 12.5% of a step towards the radius, then move to 90 degrees at 25% of the radius, and so on.

This is shown in the image below:

Now, to generate a twist we can simply add our constant step away (in the form of the 'r'(radius) graph/image) with our rotation around a circle (in the form of the 'a'(angle) graph/image). This generates our final graph:

We use this equation to sample from our texture.
In GLSL shader code, we have:

 
uniform vec2 resolution; 
uniform sampler2D tex;  
void main(void) {     
vec2 p = -1.0 + 2.0 * gl_FragCoord.xy / resolution.xy;
vec2 uv;         
float a = atan(p.y,p.x) / (2.0*3.1416);
float r = sqrt(dot(p,p))/sqrt(2.0);
uv.x = r;
uv.y = a+r;
vec3 col =  texture2D(tex,uv).xyz;
gl_FragColor = vec4(col,1.0);
}

Square color texture

To animate our spiral and make it spin, we just need to add a offset to our "a+r" value. To make the spiral scroll the texture "inwards" we can just add an offset to the "r" value.

Twist with the square color texture

This will give us our final animating spiral:

Raycasting two planes in WebGL

2011-01-28T20:22:00.000+08:00

I always implemented this effect by actually writing a complete raytracer/caster, however the version of this effect in ShaderToy greatly simplifies this effect using some old fashioned trigonometry. With some help from my old democoding partner Fractoid we generated a mathematical explanation for this routine.

In essence we use the properties of self-similar triangles to find the intersection distance from the viewer to the plane (see image below).

The camera is shown in red, and the ray from the viewer to the plane is shown in green. The height of the plane above the viewer is 'h', and the distance along the plane to the intersection point is 'd'. We can use our friend from last time, the tangent function, to find the intersection point.

For the lower triangle, if we assume one unit of travel (x) then the angle (theta) will be y / 1.

tan(theta) = y/1;

For the upper triangle, theta will be h / d.

tan(theta) = h/d;

Since the triangles are similar triangles, both theta values are the same, so we can equate these two equations. That is:

y / 1 = h / d
y = h / d
d = h / y

Now, to solve the same problem but flipped by 90 degrees for the horizontal axis we have the same formulation, except we no longer have a unit travel distance, but 'x' instead. This gives:

y / x = h / d
y = h.x / d
d = h.x / y

Now we can plug these into our texture map to give us the overall effect:


uniform vec2 resolution;
uniform float time;
uniform sampler2D tex;

void main(void)
{
vec2 p = -1.0 + 2.0 * gl_FragCoord.xy / resolution.xy;
vec2 uv;

float h = 0.25;
uv.x = h*p.x / p.y;
uv.y = 0.1*time + h / abs(p.y);

gl_FragColor = vec4(texture2D(tex,uv).xyz * p.y*p.y, 1.0);
}

You can see the result below. (You will need a WebGL enabled browser)

Disruptive Innovations

2011-01-28T13:12:00.000+08:00

Everyone wants to build a disruptive technology or a disruptive business. But what does that really mean? An article by Clayton Christensen, Mark Johnson and Darrell Rigby 'Foundations for Growth: How To Identify and Build Disruptive New Businesses' provides a description of disruptive, and identifies key requirements for disruptive businesses.

Christensen et al. distinguish disruptive innovations from staining innovations in that the latter only target existing customers in established markets. In contrast, disruptive innovations create new markets and generate new ways of doing business that effects established markets. Further clarifications:

Industry incumbents aren't always the first to market with a sustaining innovation, but they almost always end up on top due to superior resources and high stakes.
Innovations that help incumbent companies sell better products to their best customers are sustaining, not disruptive.
Established businesses move towards the more profitable customers (see above), providing asymmetric motivation for entrants to attack less profitable customers (down-market)
'Down-market' are typically small and undefined but hold the best prospects for growth

According to the article, new growth business has a 10x better chance of success with a disruptive strategy. How do you know if you can follow a disruptive strategy? In essence the recommended requirement is a open, simple, low-cost product.

Can you create a new market base?
- Does it enable customers who could not previously DIY for lack of money or skills? That is, can it become mainstream rather than specialised?
- Is it targeted at customers who want a simple product?
- Will it allow customers to do more easily and effectively what they are already trying to do? i.e. Is it fulfilling an existing need/want, rather than creating a new one?
Can you disrupt from the low end?
- Are prevailing performance good enough? If not, then a simpler product will not succeed.
- Do you have a business model that targets thin profit margins and high net asset turns. Do competitors already outsource fabrication and assembly to the lowest-cost sources?

Now that you know your innovation has the potential to be disruptive, do you have the resources, processes and values you require for success?

Resources: Do you have the best people and sufficient cash? A manager who is radically different from those established with core business who has the correct experience? Are you aware of the challenges the manager will face? Too much cash can allow bloat that weakens the product (remember our tight profit margins), too little and the product may never see the light of day.
Processes and Values: Traditional and established processes can hamper a disruptive enterprise, an independent business unit that emphasises the key values of simplicity and low-cost is best.

For established companies you will want to:

Start before you need to grow, while you can afford it (ie: while your company is still growing)
Create an aggregate project plan with strategic objectives
Train employees to scout for well positioned small companies that will help accelerate and improve your disruptive product

A successful disruptive product should generate profits almost immediately, but needs to be cautious to not out-grow your capabilities: new markets take time to emerge.

Executable compression

2011-01-26T12:20:00.000+08:00

Packing an executable to a smaller size is a common task, and the compression algorithms share a lot in common with good text compression systems. Most good executable compression algorithms have some method of interpreting, filtering or transforming the program instructions to a more compressible format. The most well-known compression algorithms are:

Run Length Encoding - where multiples of the same in-order data are represented in a compressed form. For example, the word "beekeeper", may be represented as "b(2x e)k(2x e)per", with an appropriate coding results in a reduction in size. This kind of compression works well on 8bit images and is found in image formats such as BMP.
Huffman compression - each code is represented with a number of bits proportional to the frequency of occurrence. For example, we could represent vowels with shorter bits, and consonants with longer bit sequences, or "e" could be represented with "1" and every other character with 0 plus the usual 8 bits then "beekeeper" would come to "b11k11p1r" in a total of 4x 9 bits and 5x 1 bit totalling to 41 bits rather than 72 bits.
Lempel-Ziv (LZ) - a dictionary of all previous data is kept and references are made back to the history of the data. For example, "beekeeper" could be represented as "be(-1,1)k(-3,2)p(-2,1),r" which translates to "be" plus the same character as before (-1) and one (1) byte of it, resulting in "bee", then "k", followed by the occurrence three characters before (-3) and (2) bytes of it, resulting in "beekee", etc.
Arithmetic coding is similar to huffman coding (and explained very concisely by Charles Bloom), in essence it also assigns bits according to the probability of occurrence (as a "floating point" number), and then re-scales/encodes the probabilities to fixed-point. Arturo ("Dario Phong") Campos has a concise explanation.
PAQ - this is generally considered the state-of-the-art compression algorithm. It uses conditional probabilistic models to achieve optimal compression.

There is plenty of source code around the web for these algorithms, but the Basic Compression Library provides routines for RLE (Run Length Encoding), Huffman, Rice, Lempel-Ziv (LZ77) and Shannon-Fano compression algorithms. And Matt Mahoney maintains the PAQ algorithms. There are also quite a few general executable compressors available including UPX and Mpress, both zip and 7zip can generate self-extracting executables. Microsoft CAB also performs very well (See trimmit for Mac). But the state-of-the-art in self-extracting executable compressors for small programs are Crinkler and kkrunchy for < 4kb and < 128kb programs respectively. (A good resource for various tools is available at in4k)

These compressors use a standard compression algorithm but also transform the input to a more compressible format. The most common transform algorithm is the Burros Wheeler Transform (BWT), this attempts to re-order data so that similar codes are close to each other - increasing the ability for the data to be compressed.

For executable compression patterns in the instructions stream can be leveraged to increase the compression ratio. For example, instructions often address similar areas of memory, simple delta-encoding of the address values can typically greatly increase the compression ratio.

Recently, both kkrunchy and Crinkler were described in detail. The author of kkrunchy Fabian "ryg" Giesen wrote a great blog post describing how kkrunchy works. Since kkrunchy works with larger file sizes some more intelligent tricks can be applied. Alexandre Mutel decomposed the Crinkler compressor in his blog post and posted some fabulous pictures of before-vs-after entropy of a compressed executable. Unfortunately, both of these programs are targeted at Windows PE files, and so don't work for other platforms (See here, here, here and here for tips on PE).

The usual approach to exe compression on linux/osx is just to do the modern-day version of com/cab dropping and compress your program with gzip and have a script extract and execute the program. This lacks a bit of flare, but works. Articles describing elf and mach-o are available by Brian Raiter and Amit Singh respectively, but unfortunately they are a little out of date.

A few tools have been written for linux and osx including the byte-optimized linker (x86/64) and obj stripping for linux, and iPakk and muncho for OSX (again, a bit dated). An older elf stripper is also around, and Timo Wiren gives a good overview too. Unfortunately, a similar page on OSX is no longer available online (maybe one day). All in all, I've still found your best bet on a platform other than Windows is just to follow Timo Wiren's first step of advice and do a simple dropper:

Write your program, and compile it: g++ helloworld.cpp

#include 

int main() {
printf("hello world!\n");
return 0;
}

Optional: Strip it
```
strip a.out
```
Compress it:
```
gzip a.out
```

Create the unpack script (unpack.header):

a=/tmp/I;tail -n+2 $0|zcat>$a;chmod +x $a;$a;rm $a; exit

Combine the script and zip into a final executable:

cat unpack.header a.out.gz > program
chmod +x program

Enjoy!

My a.out went from 8768 to 1153 bytes. Nice. (Using strip saves me 160 bytes on the original and 136 bytes on the final, but I'm sure you can save more by being clever about use of the gcc crt, gcc flags and throwing a few tools at this process).

Tunnel effect explained in WebGL

2011-01-11T19:33:00.017+08:00

The tunnel effect builds on the circle equation we covered in the introductory XOR bitplasma. However, this time we need to add a two more concepts. First, we need to calculate the angle of each point on the screen, relative to the origin (center of screen). To find this we can use the properties of right-angle triangles, namely the tangent function (tan). That is, the tangent of the angle is equal to opposite over adjacent.

Visualization of the angle for each pixel

By plugging in our pixel x/y coordinates we get a range from zero to pi of angles. Dividing by pi gives us a range from zero to one. In code this is:


float a = atan(p.y,p.x);
result =  a/(3.1416);

Tunnel depth

Second, we need to find the "depth" of each point in the tunnel. Luckily this is easy to do, as projecting a 3d point to a 2d viewer is just a "divide by z" operation (objects that are further away appear smaller than objects that are closer - a nicer explanation will follow in future posts). So we can just generate a gradient of circles which we can treat as the distance from the viewer (our "z" value) and invert this (ie: 1/z).

Finally to get a good effect we need to apply a texture map. So combining the two coordinates we use the angular coordinate for the "v" coordinate and the depth coordinate as out "u" value.

So the complete code for our tunnel-shader is:



uniform vec2 resolution;
uniform float time;
uniform sampler2D tex;

void main(void)
{
vec2 p = -1.0 + 2.0 * gl_FragCoord.xy / resolution.xy;
vec2 uv;

float a = atan(p.y,p.x);
float r = sqrt(dot(p,p));

uv.x = 0.1/r;
uv.y = a/(3.1416);

vec3 col =  texture2D(tex,uv).xyz;

gl_FragColor = vec4(col,1.0);
}

You can see the result below! (You will need a WebGL enabled browser)

As a small extension to this we can progressively change the power of the square function in the circle equation to generate a less and less round "curve", progressively changing the circular tunnel into a square tunnel.

Graph of increasing squares

So starting from:


float power = 1.0;
float r = pow( pow(p.x*p.x,power) + pow(p.y*p.y,power), 1.0/(2*power) );

We can slowly increase the power until we get a square-like tunnel. The image shows the effect of increasing the power term, the final bottom right two images show the contrast between the round and square-like tunnels.

XOR Demoeffect in WebGL

2011-01-09T12:57:00.037+08:00

I wanted to do a series on a set of demoeffects, inspired by Shader Toy (and Denthor!). The majority of the shader toy effects are either raytraced, or polar/circle-based. So I thought I would begin with polar/circles and work my way from there. Most of the effects are based on a number of "oldschool" democoder tricks that are easy to understand once you have the background knowledge.

I won't be covering the basics behind writing shaders, but I might do so at a later point.

All of iq's shaders are rendered using a pixel shader (or fragment shader in OpenGL talk). The first step is to calculate the position of the pixel on the screen (or canvas in case of WebGL) normalised from -1 to 1. In a picture this is:

To visualise this in the shader we could write:


void main(void)
{
vec2 p = -1.0 + 2.0 * gl_FragCoord.xy / resolution.xy;
gl_FragColor = vec4(p.x,p.y,0.0,1.0);
}

Now each horizontal value will get an increasing value of red, and each vertical value will get an increasing value of green (we are using the RGBA color space)

We can use the cartesian equation of a circle to generate a gradient of circles.

Again, to visualise this in the shader we could write:


void main(void)
{
vec2 p = -1.0 + 2.0 * gl_FragCoord.xy / resolution.xy;
float radius = sqrt(p.x*p.x + p.y*p.y);   
gl_FragColor = vec4(radius,0.0,0.0,1.0);
}

If we want to generate concentric circles we could set a boolean value on or off depending on a modulo operation. If we take the modulo of a value and then test whether it is above half-way then we can generate an on-off pulse. For example, if we get a value ranging from 0 to 1, module 0.1, we can generate a on/off pulse by testing if it is greater than 0.05.

In shader code this would be:


void main(void)
{
vec2 p = -1.0 + 2.0 * gl_FragCoord.xy / resolution.xy;

float radius = sqrt(p.x*p.x + p.y*p.y);
float modulo = mod(radius,0.1);
bool toggle = false;
if (modulo > 0.05) toggle = true;
if (toggle)
gl_FragColor = vec4(1.0,0.0,0.0,1.0);
else
gl_FragColor = vec4(0.0,0.0,0.0,1.0);
}

This is a bit long-handed, we can shorten this by directly setting the toggle value, and using the dot product to perform the square operations.
ie:


float radius = sqrt(dot(p,p));
bool toggle = mod(radius,0.1)>0.05;

Great! Now we have all the background knowledge we need to make our first interesting effect. This will be based on the XOR operation:

XOR Truth Table
Input		Output
A	B	Output
0	0	0
0	1	1
1	0	1
1	1	0

First, lets generate two different circles.


void main(void)
{
vec2 p = -1.0 + 2.0 * gl_FragCoord.xy / resolution.xy;

vec2 offset2 = vec2(0.3,0.3);

float radius1 = sqrt(dot(p,p));
float radius2 = sqrt(dot(p-offset2,p-offset2));

bool toggle1 = mod(radius1,0.1)>0.05;
bool toggle2 = mod(radius2,0.1)>0.05;

gl_FragColor = vec4(toggle1,toggle2,0.0,1.0);
}

Wonderfull! Now if we add in the XOR truth table:


//xor via if statements
float col = 0.0;
if (toggle1) col = 1.0;    
if (toggle2) col = 1.0;
if ((toggle1) && (toggle2)) col = 0.0;

gl_FragColor = vec4(col,0.0,0.0,1.0);

And we get a wonderful overlapping pattern.

Add in a bit of animation and we have our first demoeffect! Click the button below in a WebGL enabled browser (Firefox, Chrome, Safari). (view source for full code)

Future CPU/GPU architectures and OpenCL

2011-01-07T20:13:00.081+08:00

For a while x86 CPUs were just aimed at getting faster, more and more ticks. Then, there was a shift from faster to more efficient (in terms of power used / heat generated vs. performance) in the Pentium 3/4 era. Then, another shift towards multiple cores. Now, the next shift has occurred: CPU and GPU fusion. (Despite AMD talking about it for longer than I can recall. I think I was talking to an AMD VP shortly before they purchased ATI about how GPU and CPU fusion was the future.)

Recently Intel released Sandy Bridge their CPU/GPU processor, and AMD's fusion APU's have been around. Interestingly, both are targeted at laptops (the bulk of the market), and still expect discrete GPU's for high-end performance. The fusion is just a bit of a bonus.

Interestingly all those 2009 rumours about nVidia building an x86 chip turned out to be wrong, with the real product being far more interesting. An nVidia fusion product of an ARM CPU with nVidia GPU's. This might prove to be a very interesting result considering the amount of effort being put into improving the ARM architecture and the power usage concerns in both smartphones/tablets and supercomputing. With the next version of windows running on ARM there will certainly be interesting times ahead.

Intel/AMD aren't standing still on the CPU front and are pushing ahead with AVX but the real interesting part is that OpenCL is being pushed across the board. Recent publications from the UK GPU computing conference demonstrate that ARM are pushing OpenCL as their platform of choice (for both CPU and their Mali GPU, it is Clang/LLVM based), and AMD and Intel have been strong supporters of OpenCL too. Did you know Samsung supports OpenCL too?

It would seem that OpenCL has a very strong support base, and is likely the platform of choice for developers on Intel, AMD, ARM, Apple, IBM, etc. What hope does CUDA stand? It seems nVidia will eventually be forced to drop CUDA, or invest heavily into CPU-based CUDA (Hello Ocelot!) or OpenCL translation. Eventually people will tire of writing and re-writing CUDA programs as they swap between platforms.

Envision the not-so-far future where you have a workstation with multiple CPU/GPU fusion cores [non-CUDA], and a discrete fusion GPU (GPU [CUDA]/ARM [non-CUDA] core) - are you really willing to write a specific CUDA routine for just the nVidia GPU, or are you more likely to try a less optimal OpenCL routine that will then also then run on the CPU, CPU SIMD, CPU/GPU fusion and ARM cores?

It seems that the argument being put forward by nVidia to write everything in CUDA for optimal performance will not hold as you will gain more from all the other devices helping out in the computation compared to the loss from using OpenCL over CUDA.

Of course there are other choices out there such as Accelerator and RapidMind.

The UK conference reveals Microsoft's GPGPU language "Accelerator" has made progress, and now is no longer only GPU limited (it now supports SSE3 on modern CPU's). I'm still not aware of anyone using this for anything practical though, which seems to be a bit of a shame. And ever since Intel bought RapidMind (now Array Building Blocks) the tech became very Intel-specific. So neither of those choices sound too promising.

It will be interesting to see what nVidia decide to do with CUDA, how developers will adjust to fusion CPU / GPUs and what higher-level language (or language extension?) will become de-facto in the future. Stay tuned..

2010 Summary

2011-01-02T00:07:00.000+08:00

Looking back, 2010 was a big year. My life was dominated by three factors:

Our entry into MAGIC 2010, with the WAMbot autonomous robots. Our team managed to place fourth out of 23 international competitors and placed best in Australia (and Asia!). Unfortunately, due to the competitive nature of the event, I didn't blog everything I did or any of the great stuff our team put together. Hopefully I will be able to catch up on that in 2011. Popular posts on this area for 2010 were all on filtering, including alpha-beta filters, and the more advanced Kalman filters (part1) and
Kalman filters (part2).
Working at Transmin, including the commissioning of the now world-famous Transmin Grapples (controlled by a wiimote) in the UK. Popular posts on this work were realting to the collision system convex hull generation and barycentric coordinates.
Getting married in Vac, Hungary!

A bit of a departure from 2009 which was mostly focused on GPGPU, fluid simulations, physics engines, and computer graphics. I still have a backlog of content to write about from my GPGPU work in 2009, but its starting to be less relevant as the GPGPU world pushes ahead, but I'm aiming to post more in 2011 than I managed in 2010. Should be a good year!

Catchup Post: Graphics

2010-12-29T20:50:00.000+08:00

ShaderToy

Another set of interesting links:

Inigo Quilez's Demoscene Shader Toy is absolutely fantastic. It is like the modern day version of Grant Smith's (Denthor) Asphyxia Tutorials. Many demoscene effects in glsl shaders, including a whole bunch with raytracing and ambient occlusion, etc. You will need a webgl compatible browser (e.g. the new version of Chrome (v9 - currently beta)). With any luck I'll spend some time in future describing how each effect is achieved.
A web based mandelbrot fractal viewer with a google-maps interface.
A short explanation with some nice visual examples of how procedural buildings are generated in Unreal Engine 3.
Once you have built your city, you can use more procedural tools to destroy a city.
Visual glBlendFunc tool, for helping you decide what blending you would like. (Additive glBlendFunc(GL_ONE,GL_ONE) and Screen glBlendFunc(GL_ONE,GL_ONE_MINUS_SRC_COLOR) are useful ones)
Color Scheme Designer 3 helps you pick good colors.
An interesting one kilobyte javascript christmas tree with an explanation of how its done.
The tiny 3d modeler Qoob has made great progress, and the library is now public. Should help with those 64kb intros/games.
Open Asset Import Library has made good progress and can now load a large number of 3d model formats.
The OpenGL / OpenCL gDEBugger is now free.
AMD's triangle order optimization tool has had its final release.
AMD OpenCL presentation on Smooth Particle Hydrodynamics. Now everybody is doing it...

Humble Bundle #2 - Great indy games - name your price!

2010-12-24T17:21:00.000+08:00

Osmos - Humble Bundle 2

The independent games humble bundle offer is back again, better than before. It is a pay-what-you-want offer for 5 indy games, all of which have support for Windows, Mac OSX and Linux. If you pay above the average, you get the previous humble-bundle pack of 6 games as well! A very good deal for whatever you want to pay! (Makes an excellent Christmas present!) Anyone studying games design or games programming should get these games to learn from them - what works, what doesn't? Braid is a fabulous example of teaching the player the game without needing to give them a tutorial, and many of these games are great examples of the scope you should aim for if you are making your own game.

The games included are:

Braid - a side scrolling puzzle/adventure through time. Nicely designed gameplay.
Cortex Command - side scroller, not very impressive.
Machinarium - a point and click adventure game, nice graphics, pretty decent.
Osmos - an ambient physics-based "eating" game (you absorb smaller entities). Good gameplay and a great "programmer-game" (nice graphics). My pick of the lot. (only $10 separately)
Revenge of the Titans - a tower-defense (build towers that destroy enemies) game. Nothing special.

The other games are:

World of Goo - a construction puzzle game. Lots of fun.
Aquaria - an underwater fantasy game.
Gish - a platform game.
Lugaru - 3D action adventure game.
Penumbrac - a FPS/adventure game.
Samorost 2 - a flash-based puzzle game.

If you pay 10 USD to get them all, that works out to less than a dollar a game, and I guarantee you will find at least one game you think is worth $10 in the humble (cross-platform games) bundle.

Underground

2010-12-23T23:51:00.001+08:00

Few updates this month because I've been underground. And I don't mean I've joined some kind of strange sub-culture or gone in hiding, I mean literally 1.5km vertically underground to commission a Transmin automated Rockbreaker (there's not much internet down there!). A few things I learnt / experienced about hard-rock underground mines (most of which are very obvious):

Block caving is insane. The idea is to create an extraction level under the ore body, then continuously blast the ore into smaller rocks that can be processed, leaving a massive growing "sink" hole on the surface. You also need a very very very long conveyor belt.
The tunnels are quite large, as some very large vehicles need to drive through the mine.
All the tunnels have a 'clean' look to them, largely thanks to the use of shotcrete (i.e. concrete reinforcement around the tunnel rock).
It takes 45 minutes to drive down to a depth of 1.5km
When driving, give way to larger vehicles, or vehicles with explosives.
Its difficult to move around quickly, you will easily break a sweat in no time.
Batteries weigh a lot when you need to carry them around on a belt all day
You use a lot more oxygen if you panic, or move around a lot
There is a complex system of ventilation channels with really really big fans providing all the air
It is really easy to get lost in a large underground mine
There is an underground dining area. It is called the 'crib'. I don't know why.
If anything bad happens, you don't have much of a chance, especially if you are not aware of all the intimate details of how the mine operates. (ie: haven't been there for more than a year)
Explosions are loud
Ground movement is bad and very very loud
There is an awful lot of dust

All in all an interesting experience, but all the dust certainly didn't do any good for my eyes or my lungs. I've been coughing a lot even after being out of the mine for a week as the very fine dust just gets everywhere.

XV-11 LIDAR Hacked!

2010-11-26T17:34:00.000+08:00

Congratulations to the team at Random Workshop blog, Hash Salehi modified some code from Nicolas Saugnier to parse the LIDAR data in realtime!

Movie follows:

That didn't take long!

GPGPU catchup

2010-11-25T09:21:00.001+08:00

Another month, another catchup post on the world of GPU's. A few interesting things have happened:

nVidia have released the posters from the 2010 Research Summit on GPU Technology, there are a number of absolutely fantastic posters in this collection - too many to list individually!
CUDA 3.2 has been released, with H.264, random number, and sparse matrix support, along with the usual smattering of improvements.
Intel OpenCL has finally been publicly released as an alpha. Ofcourse it only targets the Streaming SIMD Extensions (SSE) for Intel CPU's. Still no word from IBM or ARM on their OpenCL implementations.
Amazon EC2 provides GPGPU capabilities now, and early benchmarks show that it performs relatively well.
General Electric have released an embedded GPU platform. This looks great, I don't know why more people haven't mentioned this. GPU's are perfect for many of the processing problems we deal with for autonomous vehicles in interpreting vision, RADAR and LIDAR data.
Matlabs Parallel Computing Toolbox has gained strong support for GPGPU's.
Vincent Hindriksen runs an interesting blog on stream computing trends.
Not sure if I've already mentioned this, but Aras Pranckevičius implemented an interesting GLSL optimizer.
Finally BehaveRT is a GPU based behavior (ie flocking) system that can control >30,000 agents at once. Check out the video below:

Microsoft Kinect and other devices

2010-11-24T13:42:00.001+08:00

The Microsoft Kinect is a very cheap 3d vision system that provides performance somewhere between stereo cameras and more expensive time-of-flight (eg:PMD) cameras. It was actually something I was hoping would come out before the end of the MAGIC 2010 competition, but unfortunately the release date was scheduled for after the end of the competition.

The device was "hacked" almost immediately after its release and it has already been widely adopted, I think this will do wonders for the robotics/computer vision/stereo-vision community. So far all we have seen are relatively simple applications, but I'm sure people will start pushing the interpretation of the data to its limits soon, especially given that game-developers are now going to be playing with this kind of data. The Wii has already done fantastic things to push the knowledge of filtering and dealing with noisy sensor data to a wider audience, and I expect the Kinect will have a similar effect.

It all started with Adafruit offering $2000 bounty for the Kinect hack, which was promptly won by Hector Martin on the 10th of November.
One of the first videos (now viral!) to do the rounds was from Oliver Kreylos showing the 3d data fused with image data and rendered in OpenGL.

Of course, it didn't stop there, other people are trying to hack the rest of the USB Kinect protocol for the inclinometer and motor controls, and trying to figure out how the Kinect IR works.

Willow Garage has already begun work on integrating the Kinect to ROS including calibration functions, and Philip Robbel managed to integrate the Kinect with a Hokuyo to do visual SLAM (using MRPT) only 7 days after the hack was released.

Hopefully we will see more practical uses for the Kinect soon! Wired published a nice story on the development path at Microsoft of the Kinect.

The best thing about this "hack" is that it has inspired others to do the same, most notably the $800 reward for hacking the Neato Robotics XV-11 vacuum cleaner LIDAR. (Whitepaper here!). At only $300 (or even $30!) for a 360 degree, 6m range, 10Hz scanning LIDAR this would do great things for the robotics community as well. Sparkfun have already made some interesting progress with their LIDAR tear-down.

Exciting times!

Batch import OBJ with Blender

2010-11-22T15:30:00.000+08:00

The OBJ importer in blender actually supports batch-import, to enable this you need to hold SHIFT when you select the importer from the File->Import->Wavefront (obj) menu. You will then be prompted to select a directory. Unfortunately, the importer will import each OBJ file into a separate (and incorrectly constructed) scene. To alter this you will need to edit the "import_obj.py" script and comment lines 1164 and 1165:

for f in files:
   #scn= bpy.data.scenes.new( stripExt(f) )
   #scn.makeCurrent()

Saves you from having to write a batch import script yourself! A great utility to convert to OBJ files from various formats (with a batch-convert mode!) is polytrans.

Team MAGICian/WAMbot takes 4th place!

2010-11-18T20:10:00.001+08:00

All of our teams hard work has paid off as we claimed 4th place in the MAGIC 2010 competition! Our system was actually very close to what the top two teams had implemented, and with a bit of luck we might have been able to snatch a prize. Maybe next time!

Above is a photo composition by Rob Reid of all the robots at the challenge stand, ordered from 1st to last (Left to Right). Team Michigan came in 1st, followed by University of Pennsylvania, and RASR took 3rd place. It's been a great opportunity to talk to all the other teams and see how they solved their problems and to see how many of the same headaches we all had. The LWC was a great place to meet and greet a number of industry people and also a nice crowd from DSTO who showed a lot of interest in what we have done. It was great to get so much positive feedback from everyone on our system.

Ram Shed Challenge

2010-11-12T20:11:00.025+08:00

The Ram Shed challenge was a media-event for the MAGIC 2010 competition. It was our first chance to see all the other teams robots and a chance to see them all at work. Our robots performed very well one the day and navigated the maze better than any other team, the entire open section of the maze was explored fully autonomously requiring no human interaction at any point. All of this despite the fact our wifi gear was mounted outside and failed during the rain, after a few minutes we were able to replace it and continue our mapping operations!

The photos show our robots at the starting line, followed by them moving off in the starting arena, then navigating the maze, and finally the prize.

A fabulous effort by our team, and I'm extremely proud of our achievements on this day!

Team MAGICian

2010-11-07T21:00:00.000+08:00

Our MAGIC 2010 test day is over, so it's time to catch up on some sleep!
Looking forward to seeing how the other teams will perform.

MAGIC 2010 - Adelaide

2010-10-31T05:48:00.000+08:00

We are off to Adelaide for the MAGIC 2010 finals.
Looking forward to meeting the other teams, and hope it doesn't rain!

Convex Hull Generation in Blender

2010-10-27T10:43:00.000+08:00

Convex hulls are very useful for a number of optimized calculations such as fast intersection tests, fast spatial subdivision, and other early-out's used in computer graphics, computational physics and robotics.

When I implemented convex hull generation and convex decomposition in PAL I first used qhull and leveraged code from tokamak physics, but then used code by Stan Melax and John Ratcliff for PAL. Recently my work at Transmin has required generation of a number of Convex hulls, and so I combined these snippets of old code to create a plug-in for Blender.

The Blender plugin creates a bounding convex hull of the selected object.
It calls an external executable 'convex' which creates a convex hull based on an intermediate OBJ file.

Installing the plugin requires you to compile the code to generate the 'convex' executable, and copying the python code into Blender's scripts directory.

To compile the C code on linux/osx:

g++ createhull.cpp hull.cpp -o convex

Place the object_boundinghull.py script in your ".blender/scripts" directory.

On OSX Blender default installs to:

/Applications/blender-2.49b-OSX-10.5-py2.5-intel/blender.app/Contents/MacOS

Once the plugin is installed you can start creating convex hulls. You can select an object in blender and cut it into smaller objects to manually decompose the hulls. To do this, you can use the Knife tool (K) or split objects in edit-mode with 'P'. (Selection tools like 'B' and manual alignment of cameras ('N', Numpad 5) will help a lot).

Once you have the objects you would like to generate hulls for select one, and run the "Bounding Convex Hull" script. It will ask you to confirm the creation of the hull. The new hull will have the same name as the original object and have ".hull" appended to its name.

The plugin will generate a new object that represents the convex hull of the selected object, with the same transforms as the original object. (Ctrl-A to apply all down to the mesh, note: Blender 2.49 does not let you apply translation transforms, but Blender 2.5+ does). You can then decimate the hull to reduced the number of tri's used to represent your object. (Editing F9, under modifiers, select 'Add Modifier', decimate, and reduce the ratio).

Now your ready to export your scene for all your raytracing and collision detection needs!

Thanks to Transmin Pty Ltd for allowing me to release this plugin back to the Blender community under the GPL.

Follow the link to download the Blender Bounding Convex Hull plugin to generate editable bounding volumes directly in Blender.

Using BZR

2010-10-10T18:18:00.002+08:00

BZR supports a number of different workflows. The most common one is "Centralized", which allows you to use BZR just like CVS or SVN. You just type "bzr commit" (save changes) and "bzr update" (get changes).

However, BZR has the advantage of being a distributed system and thus gives you the option of branching, working remotely (and still having version control), and then merging your changes back to the main trunk.

You can do this in a few easy steps:

Make a copy of your code, by making a new "branch" of the code. Example:
```
(On LOCAL)
bzr branch WAMbot WAMbotAdriansBranch
```
In future, you can keep this branch up to date by using "bzr pull" from the branch.
Copy the branch to your target (eg: a robot / embedded PC or usb-stick). If you copy from the USB stick to the target you will need an extra step to go back.
Work with the source code on the target. After you have made changes just type "bzr commit" (on the target). This will commit to your local branch.

Now you have the advantage of being able to revert any changes that you make while working away, without needing a connection to the main server.
If you copied from the USB stick, and you want to save the changes back to it, type (at the target): "bzr push LOCATION" (Where LOCATION is the USB disk drive). Example:
```
(On TARGET)
bzr push "e:/WAMbotAdriansBranch"
```
from the bzr directory on the robot.
Now merge with your local repository, from your own bzr directory type:
bzr merge LOCATION (Where LOCATION is the USB disk drive, or shared folder) Example:
```
(On LOCAL)
bzr merge X:\WAMbotBranch
```
Now you can commit them to the central server! (Just use bzr commit like always)

This saves you from having to keep track of your source code and merge things manually. Some more helpful BZR tips:

bzr update (get the latest code from the server)
bzr commit (save your code to the server)
bzr add (add some files to repo)
bzr whoami (get/set who you are)
bzr revno (get current revision number)
bzr diff -r REVISION (eg: 1000) filename (tells you the differences in a file since a specified revision)

There are a number of revision flags:
- bzr diff -r last:5 (compare with 5 revision ago)
- bzr diff -r date:yesterday (compare with yesterdays revision)
- bzr diff -r date:YYYY-MM-DD (compare with a dated revision)
bzr commit --local (commit to your own local repository, so you can easily undo changes. Note: you may need to bind/unbind, so branching as described above is probably better)
bzr revert (undo your changes)
bzr log (show commit comments)
bzr log -r REVISION.. (show all comments since given revision. Example: "bzr log -r1000..")

BZR also has a number of plugins, including one to run a command before a commit.

Circular Motion in 2D for graphics and robotics

2010-09-24T14:51:00.000+08:00

For a number of applications circular motion in 2D is useful, in particular simplified kinematic representations for mobile robot simulation and control. There are a number of different ways of representing this motion.

First it is helpful to remember a position on a circle can be described parametrically by:
[x,y] = [r*cos(theta), r*sin(theta)]
or alternatively, r =sqrt( x^2 + y^2).

As a circular variation of the standard 2D particle, we just add an angular velocity (omega) and angular orientation (theta). For a standard 2D particle we can describe its velocity (v) in terms of acceleration (a) and a delta in time (dt) (v += a*dt; x+= v*dt). We can modify this to include the parametric circle representation:
```
theta += omega * dt;
x+=v*dt*cos(theta);
y+=v*dt*sin(theta);
```
The problem with the above method is that it is in-exact and relies on an integrator. The 2D velocity/angular velocity representation can easily be fully solved analytically. The radius of a circle produced by a given velocity (v) and angular velocity (omega, or w) is:
r = | v / w |
We can modify the parametric representation to include an offset for the centre of motion:
[x,y] = [r*cos(theta) + xc, r*sin(theta) + yc]
Thus, given an initial x,y,theta we can find the centre of the circle of motion as:
```
xc = x - (v/w)*sin(theta)
yc = y + (v/w)*cos(theta)
```
Now we can update the position of the robot:
```
theta += w * dt;
x = xc + (v/w) sin(theta)
y = yc - (v/w) cos(theta)
```
We can expand this into a single line as:
```
x+= -(v/w)*sin(theta) + (v/w)*sin(theta+w*dt)
y+= -(v/w)*cos(theta) - (v/w)*cos(theta+w*dt)
theta += omega * dt;
```
Which is the form many robotics papers use.
Finally, we may wish to represent the motion in terms of two given x,y coordinates and solve for the translation and rotation required to reach them (as is the case for odometry calculations). In this case, we can represent any movement from an original set of coordinates [x,y,theta] to a new set [x',y',theta'] as first a rotation and translation to bring you to any new x' and y', followed by another rotation to bring you to the final theta'. Using triangle trigonometry this is:
```
deltaRot1 = atan2(y'-y,x'-x) - theta
deltaTrans = sqrt( (x-x')^2 + (y-y')^2 )
deltaRot2 = theta' - theta - deltaRot1 
```

There are of course many more ways of representing circular motion, but the above are the most common in computer graphics and robotics.

Intel Compiler on Linux

2010-09-14T09:21:00.000+08:00

Make sure you have access to root. (eg: sudo su root, passwd)

Make sure you have your build environment set up. eg:

sudo apt-get install gcc
sudo apt-get install build-essential
sudo apt-get install g++
sudo apt-get install rpm

ICC requires older standard C libraries, libstdc++5, so you can get them for Ubuntu from:
Package: libstdc++5. You just need to download the i386 package. (eg from the Australian mirror, by using wget [url]), and then install it, eg: "sudo dpkg -i libstdc++5_3.3.6-18_i386.deb".
If you don't do this you may get the following error messages:
```
Missing critical pre-requisite
-- missing system commands

The following required for installation commands are missing:
libstdc++.so.5 ( library)
```
Download ICC
Unzip (tar -xvf filename)
./install.sh
Choose to install for all (1)
Read "welcome" message follow instructions for licence, etc.
Activate your software (1) and provide the serial number that came in your email. You should see "Activation Completed Successfully"
Install the software (requires 3.35 gigs). You should see a message "Checking the prerequisites. It can take several minutes. Please wait…".

You might see:

Missing optional pre-requisite
-- No compatible Java* Runtime Environment (JRE) found
-- operating system type is not supported.
-- system glibc or kernel version not supported or not detectable
-- binutils version not supported or not detectable

The JRE you need for the visual debugger, otherwise you can safely continue.

The installer then asks which components to install, eg "Intel(R) C++ Compiler Professional Edition for Linux*", just press "1. Install" to continue. It should state "component installed successfully."
Setup the paths, you can use the iccvars.sh in /opt/intel/Compiler/11.1/073/bin to setup everything for you. (eg: source /opt/intel/Compiler/11.1/073/bin/iccvars.sh ia32). You may wish to put it into your .bashrc file.
That's it! Type "icc" to invoke for C files or "icpc" for C++ files. For standard makefiles use "make CXX=icpc"

On a 1GHz VIA Esther processor, GCC 4.4.1, with -O2 -march=c3-2:

real 0m16.855s
user 0m16.849s
sys 0m0.004s

And, with ICC 11.1, with -O2:

real 0m11.369s
user 0m11.361s
sys 0m0.008s

An instant 45% speedup! Unfortunately not all code makes such a big change, some other compute-intensive code I tested only got a 4% speedup. In any case I'd say its worth it!

SIGGRAPH 2010 Course Papers Overview

2010-09-12T19:58:00.000+08:00

I've managed to work through the SIGGRAPH 2010 course content that relates to realtime rendering. I quite liked the Toy Story 3 rendering techniques and realtime rendering survey by nVidia- just because they give a nice overview. As always, there are a number of great presentations, and I've listed the ones that I found interesting below.

Toy Story 3 : The Video Game Rendering Techniques from Avalanche Software gives a great (211 page!) overview of a number of lighting issues for the game including SSAO (various optimizations/approximations for how/where to sample, faking more samples and dealing with large differences in depth), ambient lighting (without needing to bake it or do GI) and various aspects on shadows. A great read!
Surveying Real-Time Rendering Algorithms by David Luebke from nVidia gives an excellent short overview of a number of recent developments in realtime rendering algorithms including stochastic transparency (ie : transparency via random sampling), sample distribution for shadow maps (partitioning the scene in light-space), alias-free shadow maps, append-consume order-independent-transparency (sorting per-pixel & linked-lists), progressive photon mapping, image-space photon mapping, ambient occlusion volumes (how to speed it up with bitwise occlusion mask for each triangle - one per edge, and one for the triangle plane), stochastic rasterization (of 4d triangles)
Keeping Many Cores Busy: Scheduling the Graphics Pipeline by Jonathan Ragan-Kelly from MIT gives a great overview of the graphics pipeline stages (from Input Assembler, Vertex Shader, Primitive Assembler, Tesselation, Geometry Shader, Rasterizer, Pixel Shader, and finally Output Blending) and load balancing.
Uncharted 2 - Character Lighting and Shading by John Hable from Naughty Dog gives a fabulous overview of rendering issues with skin (in a lot of detail!), hair and clothes.
Bending the Graphics Pipeline by Johan Andersson from DICE describes tile-based deferred shading (for GPU and SPU), morphological antialiasing and analytical ambient occlusion.
A real-time Radiosity Architecture for Video Games by Sam Martin and Per Einarsson from DICE/Geomerics introduce the 'Enlighten' system for realtime GI - it gives a nice overview.
Evolving the Direct3D Pipeline for Real-time Micropolygon Rendering by Kayvon Fatahalian from Stanford University gives an interesting insight on Micropolygon rendering on current GPU pipelines.
Water Flow in Portal 2 by Alex Vlachos - I've already written about this previously, just another realtime technique for faking the simulation and rendering of water flow.

Making Concept Real For Borderlands by Gearbox Software contains some nice examples of their concept art, the development change from photorealistic to stylistic rendering and art (and the code/artist balance), and the sobel edge filter they used.
The notes from the volumetric course was broken into parts:
1. "Resolution Independent Volumes" - which describes the "Field Expression Language Toolkit", cloud modelling (via density displacement), morphing objects (by using the Nacelle Algorithm to generate warp fields), cutting models, fluid dynamics, gridless advection, and semi-lagrangian mapping (balancing between grids and non-grids).
2. "Mantra Volume Rendering" - this describes the volume rendering engine for Houdini.
3. "Volumetric Modeling and Rendering" describes the volumetrics library/API developed at Dreamworks.
4. "Double Negative Renderer B" (used in Batman Begins, Harry Potter, etc.) describes the workflow and various shaders (Fluid, Particle, Voxel, Fire, Smoke) in DNB
5. "Volume Rendering at Sony Pictures Imageworks". The section from Sony Imageworks included an overview of their pipeline and content on their open source field/fluid tools.

Catchup Post: Graphics & GPU's & Physics

2010-09-08T22:36:00.000+08:00

A long overdue catchup post for various interesting things I've spotted over the last two or three months. SIGGRAPH recently finished, so it really deserves a round-up, although I haven't had time to review all the interesting things.
The annual tutorial on
realtime collision had some interesting presentations, I quite liked the one from Erwin Coumans (Bullet) this year - it gives a good overview of the recent advances in the Bullet engine including the GPU optimizations. Simon Green also has a presentation on CUDA SPH rendering (also see Jihun Yu's particle fluid surface reconstruction) and another open source GPU SPH simulation from HPC lab.
The realtime graphics tutorial, stylized rendering, volumetrics, and programmable shaders has some great stuff that I'll look into in more detail in a future post. Ofcourse there is also always the SIGGRAPH 2010 papers list, and SIGGRAPH asia papers (again more on this later..).

Some GPGPU software/links:

AMD's Stream SDK - the new version allows printf in OpenCL kernels - very handy for debugging and OpenCL1.1 support.
AMD's OpenCL sample page.
an interesting article on larrabee's demise
CUDA Vision Library - another library, but this one has quite a few functions including optical flow and hough transforms plus some color space conversions.
AMD OpenCL tutorial.
OpenNL has some GPU based sparse matrix structures and iterative linear systems & least-squares solvers, etc.
Back40 has a fast radix sort.
OpenCL and OpenGL interoperability particle system example.
and a now-old-hat story on theGPU supercomputer in the top 500 list.

and MPTL is a parallel version of the STL algorithms.

Some physics links:

A new version of the PhysX SDK is available with some SSE optimizations and the source code to the tetgen program. A new version of the PhysX visual debugger is also available.
Creature Control in a Fluid Environment - an interesting paper, reminds me that I should really publish my PhD at some point...
While we are on the topic of underwater physics, Underwater Cloth Simulation with Fractional Derivatives is worth a look.
Example based wrinkles for cloth simualtion an interesting take on one of the more difficult aspects of good cloth simulation.
FASTCD - fracture aware collision detection - a lot of good things coming out of KAIST recently in this field.
Dynamic Local Remeshing for Elastoplastic Simulation, is a Finite Elements method for achieving a range of physical material behaviors. Neat.

Some graphics links:

Alex describes the making of the Ergon 4k intro
ryg has a great post on optimzing packed pixel blend operations for non-SIMD systems.. nifty! I wish I knew this previously! (ryg also has an interesting post on morton-codes, which you can use for organizing your data for easy n-dimensional nearest neighbor retrieval. See codexon's explanation.
I stumbled upon this interesting description of a global illumination shader including ambient occlusion, GI, bump maps, etc.
Kyle has a post on his implementation of
animating water with flow-maps
The excellent page on screen space ambient occlusion at Meshula has been updated.
NASA released a collection of NASA 3d Models
Auld's blog has some interesting posts describing his 4k modeling tool, with some input from iq.
GL minify to compress GLSL shaders.
Steve Hollasch has a nice
collection of interesting graphics-related newsgroup posts.

And finally a documentary on the history of the Future Crew demo group and Second Reality. Brings back the memories.

Kalman filters - Part 2

2010-08-25T21:47:00.000+08:00

In a previous post I described kalman filters and gave a very simple example of a 1D filter implemented in C. In the real world, having a filter with three or more inputs is common. A standard 3rd order example would be a filter that considers the position, velocity and acceleration of a system.

In this case you would have a 3x3 measurement matrix (H) (with the diagonal set to what you can measure), a 3x3 process noise matrix (Q), a 3x3 measurement noise matrix (R), and a 3x3 state transition matrix. The standard transition matrix would simply contain v+=a*dt, x+=v*dt, but we can use a 2nd order leapfrog integrator to get better accuracy of our position from our acceleration data. So in total we have:

You can either solve this using the standard kalman matrix maths, but you will find that an SVD approach will give you more stable solutions. OpenCV is one library that already has the kalman matrix maths built in. To set up a kalman filter with OpenCV we just need to setup the matrices we need and call the appropriate cvKalman functions.

(ugly) Code snippet follows:

#ifndef KALMAN_H
#define KALMAN_H

/** OpenCV Kalman filter for 1st, 2nd and 3rd order position, velocity and acceleration data.
    (c) Adrian Boeing
    www.adrianboeing.com
 */
#include <cv.h>

typedef enum {
    K_P = 1, //position only
    K_V = 2, //velocity only
    K_A = 4, //acceleration only
    K_PV = 3, //position & velocity
    K_PA = 5, //position & acceleration
    K_VA = 6, //velocity & acceleration
    K_PVA = 7 //position, velocity and acceleration
} Kalman_e;

class KalmanPVA {
public:
    KalmanPVA(int order, Kalman_e type, float initial_pos, float initial_vel, float initial_accel, float dt, float process_noise[3], float measurement_noise[3]) {
        m_order = order;
        //create the OpenCV kalman structures
        kalman = cvCreateKalman(order, 3, 0 );
        z = cvCreateMat(3,1,CV_32FC1);
        
        //construct the transition matrix
        SetDT(dt);
        
        //enable only the measurements we have!
        for (int i=0;i<m_order;i++) {
            cvmSet(kalman->measurement_matrix,i,i,((type&7)>>i)&1);
        }
        //configure the process noise matrix
        cvSetIdentity( kalman->process_noise_cov,    cvRealScalar(1) ); //zero the matrix 
        for (int i=0;i<m_order;i++) {
            cvmSet( kalman->process_noise_cov,i,i, process_noise[i] ); 
        }
        //configure the measurment noise matrix
        cvSetIdentity( kalman->measurement_noise_cov, cvRealScalar(1) ); //zero the matrix
        for (int i=0;i<3;i++) {
            cvmSet(kalman->measurement_noise_cov,i,i,measurement_noise[i]);
        }
        cvSetIdentity( kalman->error_cov_post,cvRealScalar(10) ); //large initial unknown
        
        //setup the initial state
        cvmSet(kalman->state_post,0,0,initial_pos );
        if (m_order>1)
            cvmSet(kalman->state_post,1,0,initial_vel);
        if (m_order>2)
            cvmSet(kalman->state_post,2,0,initial_accel);
        
        
    };
    void SetDT(float dt) {
        //3rd, 2nd, and 1st order transition matrix models
        
        //3rd order uses 2nd order leapfrog integration
        float F3[] = {   1, dt, 0.5*dt*dt,
            0,  1, dt,
            0,  0,  1};
        
        float F2[] = {   1, dt, 
            0,  1};
        
        float F1[] = {1};
        
        switch (m_order) {
            case 3:
                memcpy( kalman->transition_matrix->data.fl, F3, sizeof(F3));
                break;
            case 2:
                memcpy( kalman->transition_matrix->data.fl, F2, sizeof(F2));
                break;
            case 1:
                memcpy( kalman->transition_matrix->data.fl, F1, sizeof(F1));
                break;
        }
    }
    void SetMeasurements(float pos, float vel, float accel) {
        cvmSet(z,0,0,pos);
        //if (z->rows>1)
            cvmSet(z,1,0,vel);
        //if (z->rows>2)
            cvmSet(z,2,0,accel);
    }
    
    void Update(){
        const CvMat* y = cvKalmanPredict( kalman, 0 );
        cvKalmanCorrect( kalman, z );
    }
    float GetPositionEstimate() {
        float v = cvmGet(kalman->state_post,0,0);
        return v;
    }
    float GetVelocityEstimate() {
        if (kalman->state_post->rows>1)
            return cvmGet(kalman->state_post,1,0);
        return 0;
    }
    float GetAccelerationEstimate() {
        if (kalman->state_post->rows>2)
            return cvmGet(kalman->state_post,2,0);
        return 0;
    }
    float GetPositionError() {
        return cvmGet(kalman->error_cov_post,0,0);
    }
    CvKalman* kalman; //openCV Kalman filter
    CvMat* z; //measurement matrix
private:

    void cvKalmanNoObservation() { 
        cvCopy(kalman->error_cov_pre, kalman->error_cov_post); 
        cvCopy(kalman->state_pre, kalman->state_post); 
    } 
    int m_order;
    
};

#endif

CAD packages

2010-08-17T15:24:00.001+08:00

Some basic knowledge of CAD packages never hurt anyone. Two of the most common ones used in industry are AutoCAD and SolidEdge. Most of the time you will just need to take measurements from some diagrams rather than build a complete model.

AutoCAD has a command line interface (from way back in the DOS days). Two useful commands for measurement are:

di - Measure a distance between two points
id - Print the coordinates of a point of interest

Other things you might find yourself doing include drawing lines and circles, which are all relatively self-explanatory. Occasionally you need to measure something relative to a reference line or base line that you want to project through the whole drawing. You can do this by using the 'extend' option to lengthen the line. Simply choose the 'Extend' option from the modify menu and draw a line to represent the boundary of the lines extension, right click, and select the line you wish to lengthen. AutoCAD will lengthen the selected line up to the boundary you specified.

Like Photoshop AutoCAD also has layers which you can work with. You can turn layers on/off by clicking on the lightbulb function.

With SolidEdge you can use the dimension menu to make measurements (Make sure you are working on the correct sheet!). These can be either horizontal/vertical, by two points, or you can select an element in the drawing to use as the axis (easier than in Autocad!).

Computing events in Perth

2010-08-06T20:59:00.000+08:00

GameJam is on again in Perth - I didn't see much about it this time, but it is in Joondalup again. Also, there is a GPU computing workshop on the 19th of August in the ARRC auditorium. More information on the workshop is available here.

A star (A*) pathplanning

2010-08-05T20:09:00.002+08:00

Previously I wrote about Dijkstra, this time I'm going to look at heuristic or "AI" style approach the A* algorithm. This is a single-source single-goal pathfinding algorithm. In essence this algorithm "guesses" or estimates the distance that remain to get from a node to the destination node. These estimates guide the direction of the path (i.e. search), with each node that is visited updating the true cost of the path, until a solution is found.

A* considers what to do at each node depending on an overall heuristic score. The total score is a function of the cost of the path that has already been traversed (the "g" cost) and the estimated cost of traveling from the node to the destination (the "h" cost). There are many ways to estimate the "h" cost, typically for pathfinding problems the euclidian distance is used, however it is always better to over-estimate the remaining cost (so you will explore more feasible solutions), and so a common measure used is the manhattan distance.

The A* algorithm works on two lists, a "Closed" list of already explored nodes, and an "Open" list of nodes yet-to-be-explored.

In essence the algorithm is:

Select a source node to operate with (eg: the start node, or the node with the lowest overall cost)
For each node connected to the source node:
- Calculate the already-traveresed cost
- If the node is on the closed list, and the newly calculated traversed cost exceeds the existing traversed cost for the node, skip the node, otherwise remove it from closed.
- Calculate the estimate cost to find the total cost, and store all these costs with the node.
- Add the node to the Open list
Add the source node to the Closed list

In Pseudo-Code (from Bryan Stout):

priorityqueue Open
 list Closed 
s.g = 0 // s is the start node 
s.h = GoalDistEstimate( s ) 
s.f = s.g + s.h 
s.parent = null 
push s on Open 
while Open is not empty 
  pop node n from Open // n has the lowest f 
  if n is a goal node 
    construct path 
    return success 
  for each successor n' of n 
    newg = n.g + cost(n,n') 
    if n' is in Open or Closed, and n'.g < = newg 
      skip 
    n'.parent = n 
    n'.g = newg 
    n'.h = GoalDistEstimate( n' ) 
    n'.f = n'.g + n'.h 
    if n' is in Closed 
      remove it from Closed 
    if n' is not yet in Open 
      push n' on Open 
  push n onto Closed 
return failure // if no path found

A great interactive demonstration program can be found here: http://www.policyalmanac.org/games/aStarTutorial.htm And some source code for A* is available from the GrinningLizard website (The same author as the fantastic tinyXML library!) Keep in mind that waypoint-based AI navigation for games is a very mid-nineties approach, nav-mesh's are certainly the way to go! For an example of issues with waypoint approaches take a look at this video:Your best bet for navmesh research is Mikko Mononen's blog.

Using Parallel Reduction to Optimize Dijkstra

2010-08-04T19:53:00.001+08:00

In a previous blog post I wrote about Dijkstra's algorithm. One optimisation to the naive implementation is to calculate the minimum cost node in parallel - since this can often be the most time consuming operation for large graphs. This is a perfect candidate for a parallel reduction operation.

In serial, if we wished to sum up an array (x) of numbers, the code would be:

int sum = 0;
for(int i=0; i < N; ++i) 
 sum += x[i];

However, in parallel we could speed this up by summing parts of the array and then adding those parts together. For example, to add four numbers a,b,c,d we could first add a+b and c+d in parallel, then sum ab+cd. This is called a 'reduction' operation, and it allows us to complete an otherwise O(N) operation in O(log(N)) steps.

One particularly nifty pattern is the "Butterfly" pattern of adding elements. Best described with an animation:

In code this can be done as:

for (b=n/2;b>0;b/=2) {
 for (i=0;i<n;i++) { 
         t[i] = OP(sum[i],sum[i^b]); 
 } 
 for (i=0;i<n;i++) { 
         sum[i]=t[i]; 
 } 
}

(Where 'OP' can be any serial commutative operation, e.g. add, subtract, etc.)

To see how this works assume we are adding 8 elements (n=8) then for the first step:
b is 0100
and each subsequent operation will be operating on the following elements:

0000^0100:0100
0001^0100:0101
0010^0100:0110
0011^0100:0111
0100^0100:0000
0101^0100:0001
0110^0100:0010
0111^0100:0011

or in decimal:

t[0] = [0] + [4]
t[1] = [1] + [5] 
t[2] = [2] + [6]
t[3] = [3] + [7]
t[4] = [4] + [0]
t[5] = [5] + [1]
t[6] = [6] + [2]
t[7] = [7] + [3]

Now, for the next step:
b is 0010

0000^0010:0010
0001^0010:0011
0010^0010:0000
0011^0010:0001
0100^0010:0110
0101^0010:0111
0110^0010:0100
0111^0010:0101

Again, in decimal:

t[0] = [0] + [2]
t[1] = [1] + [3]
t[2] = [2] + [0]
t[3] = [3] + [1]
t[4] = [4] + [6]
t[5] = [5] + [7]
t[6] = [6] + [4]
t[7] = [7] + [5]

Finally,
b is 0001

0000^0001:0001
0001^0001:0000
0010^0001:0011
0011^0001:0010
0100^0001:0101
0101^0001:0100
0110^0001:0111
0111^0001:0110

And in decimal:

t[0] = [0] + [1]
t[1] = [1] + [0]
t[2] = [2] + [3]
t[3] = [3] + [2]
t[4] = [4] + [5]
t[5] = [5] + [4]
t[6] = [6] + [7]
t[7] = [7] + [6]

Thus, in only 3 parallel operations we have added 8 elements together. We also have the additional bonus of having broadcast the result to all of the eight parallel adding elements - allowing future operations for each processor to use the result, or in the case of a SIMD system, to mask the appropriate processors.

Here is the code in CUDA:

int i = threadIdx.x; // Thread i holds value x_i, one thread per element
 __shared__ int sum[blocksize]; 
sum[i] = x_i; //copy to shared memory 
__syncthreads(); //synchronise 
for(int bit=blocksize/2; bit>0; bit/=2) {
    int t=OP(sum[i],sum[i^bit]);  
    __syncthreads(); 
    sum[i]=t;  
    __syncthreads(); 
}

Nifty!

Dijkstra

2010-08-03T17:48:00.005+08:00

Dijkstra's algorithm is a well known algorithm for solving the single-source shortest path problem in a graph. It is a "global" pathfinding algorithm, in that it will find the optimal solution to all the other nodes in the graph (provided the graph has no negative cost edges or cycles). Unfortunately the algorithm is not very easy to run in parallel.

The algorithm requires two lists, a visited list, and a pending list, and an array of the current distances to each node, plus the precursors.

In essence the algorithm begins at a starting node, and all other nodes are added to a 'pending' list. The distances are initialised to 'infinite'. We begin at the starting node that has been specified.

1. From this node we calculate the distance to each neighbouring node. If the distance is less than the current record, we update the distance measurement (cost of getting to current node plus cost to get to neighbour node), and update the precursor to the neighbour node to be the present node.

2. From all nodes, the node with the minimum distance on the pending list is selected as the next node to visit. This new node is then added to the visited list and removed from the pending list..

It's quite simple, but an animation will really help get the point across:

In code, the algorithm is as follows:
(This code stores the graph in the "dist" array, with dist[i][j] representing an edge cost between i and j. If it contains '0' then there is no connection).

The initial loop sets the distances to infinity. The first inner loop finds the minimum cost node, the second inner loop updates the distances based on the current node.
The minimum distance to each node from the starting node is stored in the 'd' array. The visited array is used to record which nodes have already been processed.

void dijkstra(int s) {        
    int i, k, mini;         
    int visited[GRAPHSIZE];         
//initialize all distances to infinite, and set the visited nodes to none.              
    for (i = 1; i <= n; ++i) { 
     d[i] = INFINITY; visited[i] = 0; 
    }         
//set the distance to the starting node 's' to zero 
    d[s] = 0; 
//outer loop - iterate through all nodes 
    for (k = 1; k <= n; ++k) {                
//find the minimum cost node 
//if the node has not been visited, and the minimum cost node is not initialised, 
//then set the minimum cost node to the current node 
//if the distance to the current node is less than the current minimum,
//then update the minimum 
     mini = -1;                 
     for (i = 1; i <= n; ++i)                      
          if (!visited[i]&&((mini==-1)||(d[i]<[mini])))                                        
          mini = i; 
//now we have the current minimum node, set it to visited 
     visited[mini] = 1; //visit node               
//for each node, if there is a valid edge between the current minimum node 
//then calculate the cost to visit this neighbour node via the current node.
//if the cost is less than the current record of minimum costs, update the minimum cost.
     for (i = 1; i <= n; ++i)                               
        if (dist[mini][i]) //update distances                                    
        if (d[mini] + dist[mini][i] < d[i])                                                        
              d[i] = d[mini] + dist[mini][i];         
    } 
}

In future blog posts I'll look at the A* algorithm, a parallel reduction for Dijkstra and some SIMD/GPU/CUDA optimisations for an 8-connected Dijkstra.

C++ debugging tools: Gdb, CppCheck, Valgrind

2010-08-02T08:45:00.023+08:00

One of the most important parts of programming is the debugging phase, and for development, the testing phase. Some of the tools that can be used under OSX are the standard linux tools - but ofcourse, there are always a few tweeks.

CppCheck is a static analysis tool, it can find formatting issues, unused variables or sub-optimally used variables, pointer/memory issues, etc.

The install procedure for CppCheck is:

git clone git://github.com/danmar/cppcheck.git
make
sudo make install

sudo easy_install Pygments-1.3.1-py2.6.egg 
http://pypi.python.org/pypi/Pygments

cd htmlreport
sudo ./setup.py install

(The python aspect you only need for a nice html report)

Note, I had to check out v 1.44 for it to work with OSX, so after the git checkout command add the following:

git checkout 1.44
git checkout -b 144

Here is an example shell script to run cpp-check (thanks John):

#!/bin/bash
cppcheck --enable=all --xml --verbose -f -I math -I boost/boost -I src/framework src 2> err.xml
cppcheck-htmlreport --file err.xml --report-dir="CodeAnalysisReport" --title="My Project"

Just alter it to match your own include directories and source.

If you need to do any runtime debugging, GDB is the standard tool. It can be quite complex, but here is its basic usage:

gdb (program name) [this will start GDB with your program loaded]
set args (arguments) [this will set the command line parameters to your program]
break (function/bp) [eg: break lib/preprocessor.cpp:610]
r [run]
bt [trace]
q [quit]

Not as good as the MS debug tools, but its still far better than not having a debugger at all! Finally, Valgrind is a tool for memory-checking. It normally works out of the box, but I had to make some changes for OSX. Luckily Greg Parker already wrote a patch, and Cristian Draghici wrote up a blog post on compiling and installing valgrind on OSX.

WAMBOT makes it into the Finals!

2010-07-27T18:27:00.000+08:00

Just got off the plane from Europe, and I'm ecstatic to say that our team MAGICIAN / WAMBOT has made it as one of the six finalists for the MAGIC 2010 competition. Our success will help put Perth, Western Australia on the map as a place for robotics research. ECU, UWA and Thales put together a massive engineering effort to complete the robots and we had strong support from our sponsors Thales, SICK, XSens, RTI, and plenty of help from Illiarc. DSTO has allowed us to release photos of the robots and the event now, so I'm glad to be able to share some pictures of the action.

If you see any news stories on the event or would like to help our team - don't hesitate to leave a comment below!

Go Team WAMBOT!

Customising Access to Windows XP

2010-06-14T16:22:00.002+08:00

Delivering a Windows XP system to a customer, and don't want them to fiddle with settings?

First, you probably want to have your system log on automatically.
The Microsoft article on enabling autologin goes through the steps in detail. Essentially, start regedit and set HKLM\SOFTWARE\Microsoft\Windows NT\CurrentVersion\Winlogon AutoAdminLogon (SZ) to 1.

Then add whatever you want on startup to the start menu 'Startup' folder. (Documents and Settings\USERNAME\Start Menu\Programs\Startup)

This is also a good time to clear the startup menu of any other pesky programs. To eliminate system wide startup items easily you can try MSConfig (from run), but I prefer to edit the registry directly.
Check HKLM\SOFTWARE\Microsoft\Windows\CurrentVersion\Run and RunOnce and RunOnceEx. If you just want to eliminate the taskbar icons all together you can try editing HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Policies\Explorer and add a DWORD NoTrayItemsDisplay and set it to 1.

You can disable the windows keys etc using HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\Keyboard Layout\Scancode Map
For a detailed discussion see Tim's Northcode blog post, who suggests "Scancode Map"=hex:00,00,00,00,00,00,00,00,09,00,00,00,00,00,5b,e0,00,00,5c,e0,00,00,5d,e0,00,00, 44,00,00,00,1d,00,00,00,38,00,00,00,1d,e0,00,00,38,e0,00,00,00,00.

Note that this stops you from being able to use any of the windows special keys. So be careful!

Finally you want to lock down the user access rights. There are many ways to do this, the easiest is with the Group Policy editor. This Microsoft article on the Group Policy Editor describes how to get there, in essence: Start,run,MMC,Add a snap-in,'Group Policy Object Editor'.

Now you have options to edit under "User Configuration" and "Administrative Templates". Under "Start Menu and Taskbar" you can find options to disable Search, Help, etc. from the start menu. Under "Desktop" you can remove the various icons, and disable the desktop. Under "System" you can set which programs people can run. You might want to be careful not to disable regedit until you are 100% certain it is correctly setup.

Magic 2010

2010-06-11T21:22:00.000+08:00

Our June MAGIC 2010 TAP is over, and I'm very proud of my team's performance. They put in a massive effort for the site-visit.

Now time for normal life to resume, and some more regular blog posts... Right after I finish tying off the loose ends.

BZR on Windows

2010-06-04T11:22:00.000+08:00

There are a number of source code control options, popular ones include subversion (SVN) and GIT. CVS is on its way out. Python advocates prefer 'Bazaar' (BZR), which of course is a total pain to install on Windows.

The steps are vaguely:

Install python (I used 2.6, pretty straight forward, run an exe)
Install py-crypto - you need this for ssh/sftp (Again, just an exe install not too painful, just choose the right one)
Install paramiko, this is the SSH client. Once again, just an exe for the ctypes support, and a python module. Again, choose the one that matches your python version.
Now get bzr and install it.
Finally, add the python scripts to your path (advanced environment variables), and your ready to use BZR from the command prompt - still no gui!

Compared to the simple install, setup and use procedure for SVN I can see why Bazaar isn't a popular choice. I've not tried GIT, but I'd suggest trying GIT over BZR for a distributed versioning system.

Consumer Camera Streaming

2010-05-26T21:01:00.001+08:00

I've been looking for a decent cheap camera for a long time. Hooking into a consumer Camera is apparently close to impossible. This used to be a simple and common tasks. Almost all digital camcorders used to provide firewire ports and would feature a demo mode allowing you to get a cheap high-quality video stream for your PC. Firewire now has been abandoned, and for a while camera manufacturers (in particular Sony) provided USB streaming. This is now a thing of the past.

One alternative is to use a standard digital camera. Again, previously Cannon provided good support for remote capture and USB streaming, but this is something they seem to have dropped again.

There are a few options out there for those who are looking for tethered camera capturing via USB:

CHDK the Cannon Hack Development Kit supports a number of cannon cameras with a range of possible features. Again, difficult to find support for a current model.
BreezeSys provide a number of software tools for Cannon cameras, again only older models but if your really looking to do some specialized setup then this might be worth the effort.
Canon Official Camera SDK is a good option, but unfortunately only the older models are supported.
Olympus SDK supports a good range of cameras, unfortunately the only currently supported cameras are the more expensive DSLR range.
Pine Tree Camera Controller is a Windows GUI for the Olympus interface.
Nikon Camera Control (Windows) provides tethered control for Nikon DSLR cameras. (See also DIY Nikon)
SofortBuild is Mac OSX software for remote capture with Nikon cameras, but unfortunately only for the more expensive "D" series.

GPhoto is some linux software for remote capture from a wide range of Cameras. Unfortunately, none that I own. This is probably the best bet though.

Entangle a front end to Gphoto for Linux.

You can sometimes still get a Camera that supports component out - so if you get yourself a frame-grabber, then that might be a good option. A cheap firewire camera can be purchased from The Imaging Source, so that might be the best option, but is still likely to be out of the range for an amateur VJ or hobby robotics project.

If anyone has any suggestions for a cheap camcorder/camera that can provide firewire or USB streaming, please let me know!

Applying forces

2010-05-21T11:08:00.000+08:00

In many robotics, graphics, and physics applications some object must be 'moved' by applying a force. Doing this the naive way will often result in very unstable behaviour. There are a number of very simple steps that can be taken to improve the situation. First of all, don't just directly update the position from some overall calculated force (or rather, impulse in this case), instead accumulate a velocity using standard integration. That is:

velocity += acceleration*dt
position += velocity*dt

This is a good first step, and many people stop there and discover that they are still left with large oscillation problems. This is due to the poor first-order integrator (Euler) and the lack of damping. Adding damping and velocity limiting will help:

velocity += acceleration*dt
velocity = clamp(velocity, min, max)
velocity *= dampen //eg: 0.98
position += velocity*dt

Hopefully your system is acting closer to how you expected. At this point if you still have some minor oscillation and odd edge cases you can probably solve them through more advanced techniques. If your still not getting a behaviour close to what you want then try a completely different approach.

The final quick and easy step to improve performance is to improve the integrator. A simple leap-frog (velocity-verlet) integrator will provide decent performance (no need to go to RK45!):

velocity += acceleration*dt
velocity = clamp(velocity, min, max)
velocity *= dampen //eg: 0.98
position += velocity*dt + 0.5*acceleration*dt*dt

Done!

Now all your robot path-planning, navigation, graphics particle systems, and cloth-simulations will be up and running. Plenty of research papers to read if you want to keep improving it!

I'll leave you with this real life video illusion of marbles rolling up a slope:

Inverting Matrix - SVD (singular value decomposition)

2010-05-10T23:29:00.046+08:00

Every once in a while you find yourself needing to solve a set of equations, or invert a matrix, or worse yet, invert a non-square matrix (eg: pseudo-inverse for manipulator inverse kinematics path control (See: Minerva IK control image on right, work I did at TUM) or kalman filtering). This is when a handy mathematical tool 'singular value decomposition' comes in to play.

In essence the SVD decomposes a matrix 'M' into three other matrices with special properties, making them easier to manipulate. The SVD equation is:

Where:

U is a matrix whose columns are the eigenvectors of the M * M transposed matrix. (AKA left eigenvectors)
S is a diagonal matrix whose diagonal elements are the singular values of M.
V is a matrix whose columns are the eigenvectors of the M transposed * M matrix. (AKA right eigenvectors)

Discussing eigenvalues and eigenvectors I'll leave for another time, but they are quite straight-forward to calculate (get the matrix subtract a constant * I , take the determinant, equate to zero and solve, that gets you the eigenvalues!).

Now, how do you use the SVD to invert a matrix? Using a few matrix (inversion) identities (See the Matrix Cook Book, basic identity 1):

So now we just need a way to invert a diagonal matrix, which couldn't be easier. To invert a square diagonal matrix you simple invert each element of the matrix.
What if the matrix isn't square?
Well for that, we can just use the pseudo-inverse: we just invert each element of the matrix, and then transpose it. Done!

A good tutorial on the SVD can be found here by Dr. E. Garcia

Kalman Filters

2010-05-01T20:04:00.002+08:00

(EDIT: See also Kalman Filter's Part 2)
I've been looking into a number of sensor fusion techniques, including Particle Filters and Kalman Filters (EKF,UKF, etc). I was looking for something easy to implement, easy to use, and not too computationally intensive.

I've always been a bit sceptical as to the advantages of a Kalman filter over an Alpha-Beta filter, in terms of performance gained vs cost (i.e.: difficulty to implement & use). For most simple tasks, the Alpha-Beta filter seems to work fine. (Similarly ABG vs AB).

Particle filters appeared advantageous to me, as they are relatively intuitive and aren't that hard to use, and easy to extend. The difficulty in implementing them can be overcome by using an existing library,

Kalman filters in my opinion have as a major disadvantage of being difficult to use (you need to construct multiple models), but are relatively easy to implement and computationally efficient. Thus, the use of an existing library doesn't help much.

I spoke to two experts in the field, Julius Ziegler (who worked on the DARPA Grand Challenge Annieway vehicle with me) and Rob Reid (a local, working on visual SLAM with Kalman filters). Both suggested that Kalman filters would be the most appropriate choice. (Reading various papers seems to indicate a merged (E)Kalman & Particle filter approach is the winner)

Wikipedia provides an overview of Kalman filters, but the real problem is in understanding what all the symbols actually mean, and how it works.

Like alpha-beta, Kalman filters are prediction-correction filters. That is, they make a prediction, then correct it to provide the final estimate of the systems state. Alpha-Beta's don't have a natural extension to include control inputs, or system identification techniques. They are also (effectively) constrained to linear position/velocity tracking. Kalman filters can be extended to handle non-linear conditions.

In essence a Kalman filter will (vaguely):

Estimate the state (from previous)
Determine the error
Predict the next state
Predict the next error
Measure the system
Update the state calculations
Update the error calculations

Bellow are the equations that represent this process, followed by the definitions of each symbol:

x_temp_est = A * x_est(last) + B * u_control_input
P_temp = A * P(last) * A^T + Q
K = P_temp * H^T * (H* P_temp * H^T + R)^-1
x_est = x_temp_est + K * (z_measured - H * x_temp_est) 
P = (I - K*H) * P_temp

x - is the state we want to estimate (e.g. position)
u - is the input to the control system (if it exists) (e.g. a force)
A - state (model) matrix, how to get from last state, to next state (e.g.: position += velocity *dt). (Some people (eg: engineers) use an alternative notation 'F' for this matrix)
B - is the input matrix (Some people use an alternative notation 'G' for this matrix)
H - is the measurement matrix (what are we measuring?) e.g.: position or velocity, etc.
Q - is the process noise covariance matrix (you just 'know' this)
R - is the measurement noise covariance matrix (likewise, you 'know' this, usually from measurements, data sheets, etc, ie: how noisy are your sensors?)
P - the estimate error covariance matrix (calculated)
K - the kalman gain (calculated)

The things you must 'know' are:

How your system moves from one state to the next (e.g. given a current position, velocity, change in time, what will the next state be?) => This is the 'A' or 'F' matrix
What are you able to measure? (Maybe just acceleration, or just position?) => This is the H matrix
The amount of noise in your measurements and the state-transitions (e.g. the standard deviation of the signal noise, and how 'wrong' your simplified model of the state-transitions are) => These are Q and R matrices

Completely confused? Good. Some examples will help clear this whole mess up. First, a simple example where we are observing a noisy-constant. (e.g. measuring the height of a water-tank with a poor quality sensor) We have no control input so we can ignore the B and u terms. We have no state-transition model (it is a constant!) so we can set A to identity (i.e. one). Our first equation becomes:

x_temp_est = x_est(last)

Subsequently the second equation becomes:

P_temp = P(last) + Q

Where Q is our estimation of the variance in our state transition. Since we are measuring a constant, this value should be small. (Remember the real world always has noise, so assuming zero noise is always a bad idea) We measure the state directly (i.e. the noisy value of the constant) so the H matrix is also identity. This means:

K = P_temp * (P_temp + R)^-1
x_est = x_temp_est + K * (z_measured - x_temp_est) 
P = (1- K) * P_temp

Again, we keep R since that is our all-important measurement noise estimate. Now let's see this in action in C:

/** A simple kalman filter example by Adrian Boeing  
 www.adrianboeing.com  
 */  

#include <stdio.h> 
#include <stdlib.h> 
#include <math.h> 

double frand() { 
    return 2*((rand()/(double)RAND_MAX) - 0.5); 
} 

int main() { 

    //initial values for the kalman filter 
    float x_est_last = 0;
    float P_last = 0; 
    //the noise in the system 
    float Q = 0.022;
    float R = 0.617;
     
    float K; 
    float P; 
    float P_temp; 
    float x_temp_est; 
    float x_est; 
    float z_measured; //the 'noisy' value we measured
    float z_real = 0.5; //the ideal value we wish to measure
     
    srand(0); 
     
    //initialize with a measurement 
    x_est_last = z_real + frand()*0.09;
     
    float sum_error_kalman = 0;
    float sum_error_measure = 0;
     
    for (int i=0;i<30;i++) {
        //do a prediction 
        x_temp_est = x_est_last; 
        P_temp = P_last + Q; 
        //calculate the Kalman gain 
        K = P_temp * (1.0/(P_temp + R));
        //measure 
        z_measured = z_real + frand()*0.09; //the real measurement plus noise
        //correct 
        x_est = x_temp_est + K * (z_measured - x_temp_est);  
        P = (1- K) * P_temp; 
        //we have our new system 
         
        printf("Ideal    position: %6.3f \n",z_real); 
        printf("Mesaured position: %6.3f [diff:%.3f]\n",z_measured,fabs(z_real-z_measured)); 
        printf("Kalman   position: %6.3f [diff:%.3f]\n",x_est,fabs(z_real - x_est)); 
         
        sum_error_kalman += fabs(z_real - x_est); 
        sum_error_measure += fabs(z_real-z_measured); 
         
        //update our last's 
        P_last = P; 
        x_est_last = x_est; 
    } 
     
    printf("Total error if using raw measured:  %f\n",sum_error_measure);
    printf("Total error if using kalman filter: %f\n",sum_error_kalman);
    printf("Reduction in error: %d%% \n",100-(int)((sum_error_kalman/sum_error_measure)*100));
     
     
    return 0; 
}

This should generate output similar to:

Mesaured position:  0.562 [diff:0.062]
Kalman   position:  0.498 [diff:0.002]
Ideal    position:  0.500 
Mesaured position:  0.563 [diff:0.063]
Kalman   position:  0.509 [diff:0.009]
Total error if using raw measured:  1.566003
Total error if using kalman filter: 0.441561
Reduction in error: 72%

More (non-trivial) examples will follow soon. In the meantime I can suggest the following resources:

http://www.cs.unc.edu/~tracker/ref/s2001/kalman/index.html
http://www.cs.cmu.edu/~biorobotics/papers/sbp_papers/integrated3/kleeman_kalman_basics.pdf
http://www.acfr.usyd.edu.au/education/multiSensorDataFusion.shtml
http://www.ee.pdx.edu/~greenwd/kalman_overview.pdf

Source code/libraries:

http://kalman.sourceforge.net/
http://bayesclasses.sourceforge.net/
http://www.memsense.com/index.php/Product-Pages/kalman-filter-library.html
http://sites.google.com/site/jordiuavs/Home/kalman_filter_by_Jordi.txt
http://www.orocos.org/bfl
http://www.scipy.org/Cookbook/KalmanFiltering

Robots and Robot Competitions

2010-04-30T12:06:00.000+08:00

I am part of an Australian team that has entered the MAGIC 2010 competition, Team WAMbot. MAGIC 2010 is an exciting challenge for coordinating multiple autonomous vehicles for mapping, surveillance and tracking tasks. This is sure to prove to be an exciting challenge that will push robots forward in terms of capabilities and reliability. Although many robots can already do similar tasks, I have not seen any demonstration of the interaction of all of these capabilities, reliably for an extended period of time.

A previous challenge that sparked great interest that was also funded by the military were the DARPA Grand Challenge's. However I believe one group has taken onboard an even more monumental challenge, the VisLab's Intercontinental challenge to cross from Rome, Italy to Shanghai, China. VisLab have a unique pure-vision approach (although I doubt they will stick to this for this particular challenge), have been a leader in the autonomous automotive field for years and have done some very impressive work. They are brave enough to walk infront of their vehicles and trust them to swerve out of the way to avoid them.

I believe the VisLab challenge will be a very tough test, unlike previous ground-breaking driving trips, like UniBW's 1000 mile autonomous journey in the 1990's that followed clean Autobahn lane markings, the VisLab's challenge will travel on unreliable roads for a much longer time and need to deal with pedestrians, animals, etc, etc. They do get the slight bonus of being able to use GPS navigation.

The VisLab guys are very friendly and helpful people, so I wish them the best of luck in this challenging and ground-breaking endeavour!

I'll leave you with some interesting Robotics videos:
This blimp seems similar to the Festo blimp, but it is powered by electroactive polymers.

And a robot balancing on a ball, not unlike the BallyBot from our lab.

And VAIL's autonomous parking has made some impact on the web, no idea why, it doesn't seem much more advanced than the autonomous parking we've been seeing for years since the DARPA Urban Challenge. Still, it is neat:

Build Systems

2010-04-29T23:18:00.000+08:00

Managing and building software packages is a big task. There are a few options on what build system you can use. Windows users prefer Visual Studio 'solutions' and 'projects', *nix users prefer Makefiles. Ideally, cross-platform tools are what everyone wants.

Some popular choices include:

CMake - a 'cross-platform' make, popular with a lot of projects. (We use it in PAL thanks to Benoit Neil's contributions). My gripe with CMake is its complexity. The fact that there is a complete book to describe it is a scary thought.
Premake - is a less popular choice (a few large projects use it, eg: ODE, PAL previously used it). It uses Lua-script, and it is my personal favourite due to its simplicity whilst still being very powerful. Premake is a bit windows-orientated, which helped me as I came from a Windows development background.
bjam, the boost build system. I've not used this one too much, but it is apparently decent.
scons, a python-based build system. I've not used it much, but it seems quite complex. (Evan Drumwright developed an scons build system for a PAL benchmark tool)

Premake (4) is quite easy to use, below is a very simple template for its use:

solution "NAME"
 configurations {"Debug", "Release"}
 targetdir "bin"
 language "C++"
 location "build"
 includedirs {"src", "."}

project "NAME"
 kind "ConsoleApp"
 files {"src/*.cpp"}
 links {"lib"}

Simply invoke with "premake vs2008" for windows, or "premake gmake" under *nix.
The lua script lets you easily extend the script to copy DLL's, set up custom include paths for each user, etc, etc.

This should help you get started with cross-platform build solutions!

Online Project Management Software

2010-04-16T23:58:00.000+08:00

Every project requires some form of tracking, whether it is a simple to-do list or a highly detailed gantt chart. At some stage a some formal planning must take place, and if you are collaborating across different physical locations an online tool can really help.

I had a few requirements:

Ability to track milestones & tasks
Sepecifiy interdependencies between tasks
Track issues/bugs (Ticketing)
A visual display of the schedule (eg: Gantt, Time/Time, or Burndown chart)

I also wanted the tool to allow different management approaches (ie: not a purely scrum-based tool), and the usual niceties such as email notifications and a blog/wiki/forum/etc. Finally I wanted all this for free (ofcourse!). The usual suggestions are Bugzilla, Trac and MediaWiki, however none of these provide all the features we needed. Some of the better products I found included:

Redmine - A free (open source) web application with issue tracking, gantt charts, email notifications, wiki, forums, time tracking, etc. Unfortunately it is still quite 'beta' but definately one to watch for the future.
Assembla - A paid web service with task management, issue tracking, some scrum support, wikis, forums, but no visual way of representing a schedule as far as I could tell.
Clocking IT - A free (closed) web service that provides project tracking, it looks great but seemed a bit too simplistic for my needs.
CodeSpaces - A paid service, but offers free accounts. Easy to use, supports visual scheduling, forums, but is tightly SVN and scrum based (card walls, stories, etc.) and the help was a bit poor. I seriously investigated this option but decided against it in the end, however I can recommend this option.
CoMindWork - A paid service, but offers a limited free version. Can be both online and installed, provides a decent visual gantt chart with task and time tracking, issue tracking, email notifications, wiki, blog, and good help videos and instructions all through making it easy to learn. A big bonus is that it directly imports and exports between Microsoft Project, integrates with BaseCamp and provides an API for import/export. It also has a bit of a plone-like feel, which I was comfortable with having used it before.

So CoMindWork was the winner for me. Some of the other promising ones I was looking at included:

Zoho projects
Unfuddle
Agile42

but since I'd found CoMindWork by then I didn't look into them into too much depth.

wxWidgets on OSX

2010-04-10T22:39:00.000+08:00

wxWidgets is one of the worst toolkits known to man. Unfortunately, people keep using it, so I need to keep compiling it. I personally prefer FLTK, my only complaint about FLTK is that it can look pretty poor. Recently I have been looking around for a very light-weight native cross platform widget toolkit - no luck so far. (Suggestions anyone?)

Here are some instructions on compling wxWidgets (ex wxWindows) for Apple Mac OSX Snow Leopard. To begin, download wxMac, decompress it, open a terminal and navigate to the base wxMac directory.

mkdir osx_build
cd osx_build

You will most probably want to have OpenGL support with wxWidgets, so remember the "--with-opengl" flag. As with most projects, the 64bit support on OSX is flaky, so it is best to compile for 32bit using "-arch i386". Hopefully this won't be necessary in the near future.

../configure --with-opengl CFLAGS="-arch i386" CXXFLAGS="-arch i386" CPPFLAGS="-arch i386" LDFLAGS="-arch i386" OBJCFLAGS="-arch i386" OBJCXXFLAGS="-arch i386"

(Note: other handy options are: --with-cocoa, --disable-shared --enable-static, --enable-unicode, --enable-debug. At present Cocoa support is dubious, again, this may change in future.)

(you may wish to confirm that opengl canvas is enabled - see:
/usr/lib/wx/include/mac-unicode-debug-2.8/wx/setup.h)

make

You should have a lib directory with all the dylib's in it.
Unfortunately, for wx to work, you will need to install it.

sudo make install

make samples

This should generate a whole bunch of samples in the osx_build/samples directory

Now you can run the samples! (Note: the samples can not be run from the command line, you need to run the applications, otherwise the program will not gain focus and you won't be able to click on any of the buttons!)

Catchup: Life

2010-04-10T22:34:00.000+08:00

I've had a very busy time, I was in the UK doing commissioning work, returned to Perth for a meeting with Thales managers about MAGIC 2010, moved house, easter, and got sick for a week.

This totally destroyed my plans for posting a whole set of catchup posts so I guess that will have to wait.

Pixelux Digital Molecular Matter engine - Free license soon!

2010-03-09T21:15:00.001+08:00

AMD have just announced there will be a free version of the DMM engine. It sounds like it will be closely integrated with Bullet Physics and provide OpenCL support.

I'm looking forward to this as DMM is the only realtime finite-element (FEM) based physics engine around. I'm interested to see how well it works.

Hopefully I can get a copy soon and some time to integrate it into the Physics Abstraction Layer.

Here is a video of DMM to refresh your memory:

Alpha Beta Filters

2010-03-02T09:19:00.001+08:00

(EDIT: See also Kalman filters)

Alpha-Beta filters are fairly well explained on wikipedia, and are generally a very easy first-stop solution before heading to Kalman or particle-filter alternatives. (The next obvious step is to extend this to include acceleration (Alpha-Beta-Gamma), and to limit the error/estimates to a sensible range for your application).

Here is a small example program showing how they work, it generates output similar to this:

Ideal     position: -0.897 -0.443
Mesaured  position: -0.890 -0.421 [diff:0.029]
AlphaBeta position: -0.898 -0.442 [diff:0.001]
Total error if using raw measured: 1.522438
Total error if using a-b filter:   1.059981
Reduction in error: 69%

C source code follows:

/** A simple alpha-beta filter example by Adrian Boeing 
    www.adrianboeing.com 
 */ 

#include <stdio.h> 
#include <stdlib.h> 
#include <math.h> 

typedef struct { 
    float alpha; //alpha value (effects x, eg pos)
    float beta; //beta value (effects v, eg vel)
    float xk_1; //current x-estimate 
    float vk_1; //current v-estimate 
} AlphaBeta; 

void InitializeAlphaBeta(float x_measured, float alpha, float beta, AlphaBeta* pab) {
    pab->xk_1 = x_measured; 
    pab->vk_1 = 0; 
    pab->alpha = alpha; 
    pab->beta = beta; 
}    

void AlphaBetaFilter(float x_measured, float dt, AlphaBeta* pab) {
    float xk_1 = pab->xk_1; 
    float vk_1 = pab->vk_1; 
    float alpha = pab->alpha; 
    float beta = pab->beta; 
    
    float xk; //current system state (ie: position)
    float vk; //derivative of system state (ie: velocity)
    float rk; //residual error 
     
    //update our (estimated) state 'x' from the system (ie pos = pos + vel (last).dt)
    xk = xk_1 + dt * vk_1; 
    //update (estimated) velocity  
    vk = vk_1; 
    //what is our residual error (mesured - estimated) 
    rk = x_measured - xk;  
    //update our estimates given the residual error. 
    xk = xk + alpha * rk; 
    vk = vk + beta/dt * rk; 
    //finished! 
     
    //now all our "currents" become our "olds" for next time 
    pab->vk_1 = vk; 
    pab->xk_1 = xk; 
} 

double frand() { 
    return 2*((rand()/(double)RAND_MAX) - 0.5); 
} 

int main(int argc, char *argv[]) {
    AlphaBeta ab_x; 
    AlphaBeta ab_y; 
    double t; //time 
    double x,y; //ideal x-y coordinates 
    double xm,ym; //measured x-y coordinates 
    double xnoise = 0; //noise we are inserting into our system
    double ynoise = 0; 
    double m_error = 0; //total error (measured vs ideal)
    double ab_error = 0; //total error (ab filter vs ideal)
#define DT 0.1
    //intialize the AB filters 
    InitializeAlphaBeta(1,0.85,0.001,&ab_x); //x position
    InitializeAlphaBeta(0,1.27,0.009,&ab_y); //y position
    srand(0); 

    for (t = 0; t < 4; t+=DT) {
        //our 'true' position (A circle) 
        x = cos(t); 
        y = sin(t); 
        //update our simulated noise & drift 
        xnoise += frand()*0.01;
        ynoise += frand()*0.01;
        //our 'measured' position (has some noise) 
        xm = x + xnoise; 
        ym = y + ynoise; 
        //our 'filtered' position (removes some noise) 
        AlphaBetaFilter(xm,DT, &ab_x); 
        AlphaBetaFilter(ym,DT, &ab_y); 
         
        //print  
        printf("Ideal     position: %6.3f %6.3f\n",x,y); 
        printf("Mesaured  position: %6.3f %6.3f [diff:%.3f]\n",xm,ym,fabs(x-xm) + fabs(y-ym)); 
        printf("AlphaBeta position: %6.3f %6.3f [diff:%.3f]\n",ab_x.xk_1,ab_y.xk_1,fabs(x-ab_x.xk_1) + fabs(y-ab_y.xk_1)); 
         
        //update error sum (for statistics only) 
        m_error += fabs(x-xm) + fabs(y-ym); 
        ab_error += fabs(x-ab_x.xk_1) + fabs(y-ab_y.xk_1); 
    } 
    printf("Total error if using raw measured: %f\n",m_error);
    printf("Total error if using a-b filter:   %f\n",ab_error); 
    printf("Reduction in error: %d%% \n",(int)((ab_error/m_error)*100));
    return 0; 
}

Catchup: Graphics Links Post

2010-03-01T22:34:00.000+08:00

Again, a set of interesting links from the last few weeks:

Simple and Fast Multimedia Library, a SDL replacement with a few more modern concepts. (eg: shaders!)
The OpenCL debugger, gDEBugger CL is in public beta for Windows, Mac OS X and Linux.
ATI Stream Software Development Kit (SDK) v2.01 now supports DirectX / OpenCL interoperability, plus debugging with GDB! A giant leap forward for OpenCL by AMD!
Sander Van Rossen has put together a set of interesting posts on implementing a constructive solid geometry (CSG) system.
OpenRL (raytracing language) has gone beta. I've not had positive experiences with Caustic so far. Wait and see I guess.
Apparently, someone managed a 20x speedup for SQL select queries with the GPU. I guess I need to eat my words. I'm still not convinced that this is really a CPU-intensive issue. (Maybe for scheduling and retrieving flight prices - a dijkstra-like issue)
An interesting article on the history of photoshop, never realised how humble the beginnings were, and how much influence one mans decision to allow optional extras (ie: plug-ins) played on the future of the product.
I never realised this, butAutodesk has a massive price reduction for students, this includes 3ds Max, Maya, and AutoCAD. Wow!

And, as per usual, I'll finish off the catchup post with some neat videos. First, one that I think does a great job of explaining the animation process, and then a neat video showing just how far CG has come in film. (I recall speaking to Paul Debevec about Spiderman, and he said the director decided to redo all the actors in all scenes in CG since they looked better and they had more control over facial expressions,etc.)
Cirkus Animation ABC:Stargate studios reel:

Profiling on Mac OSX with Saturn

2010-02-19T17:55:00.000+08:00

It is always advisable to profile your code before trying to optimize it. It is often most helpful to role your own (using timers & counters), but often a quick and simple tool will help a lot.

For windows I like the very sleepy profiler. On Mac OSX Apple provide the Saturn profiler (See: Saturn profiler user guide).

To demonstrate we can try compiling a small program:

#include <math.h> 
#include <stdio.h> 

#include <saturn.h> //include the saturn profiler

double func1(double x) { //do some maths
    return sin(x)*cos(x); 
} 

double func2(double x) { //do some more maths
    return pow(x,3); 
} 

int main() { 
    double x=0; 
    double z=0; 
    startSaturn(); //being profiling 
    for (x=0;x<100;x+=0.01) {
        z+=func1(x)+func2(x)*tan(x); 
    } 
    stopSaturn(); //end profiling 
    printf("z:%f\n",z); //make sure compiler doesn't throw our computations away
    return 0; 
}

Now we need to compile it with profiling support:

g++ x.c -finstrument-functions -lSaturn -m32 -O2

Some common problems include:

```
Undefined symbols: ___cyg_profile_func_enter
```
This comes from the -finstrument-functions option : it requires a special hook for each function - this is provided by saturn, so you must link with it.
```
ld: warning: in /usr/lib/libSaturn.dylib, file is not of required architecture
Undefined symbols: _startSaturn
```
Again, either you forgot -lSaturn, or you have remembered it, but are using a 64 bit OS/chip. Specify '-m32' to force 32bit mode.

If it all compiled succesfully, then start Saturn and choose 'Saturn', 'Launch Process'. Then select the executable (eg: a.out) in the dialog box.

Press OK, and Saturn will run and profile your program, and generate a folder with the profiler output data. (eg: Saturn_profile_a.out.000)

You can then select the data file to view the output, and Saturn will display a call graph and the amount of time spent in each function. Now the fun of optimizing can begin. Enjoy!

Intersection of a Convex Hull with a line segment

2010-02-18T15:55:00.000+08:00

A ray, or line segment can be represented parametrically as:
S(t) = A + t(B-A)
Where A and B are the endpoints of the segment, and t is the parameter that ranges from –infinity to +infinity for a ray, or just 0..1 for a segment.

A plane can be represented as n.X = d, where n is the plane’s normal, and d is the offset. (Given the plane’s normal, and a single point on the plane, P, we can calculate: d = -n.P)

A convex object can be represented as the area contained within a set of planes. Thus, to find the intersection between a line segment and a convex object, we just need to clip it against all the planes that form the convex object.

First, substitute the line equation into the plane, and solve for t:
i.e.:
n.(A+t(B-A)) = d
n.A + t*n.(B-A) = d
note: using identity ru.sv = rs(u.v), where u,v are vectors, and r,s are scalars
re-arrange to solve for t, the intersection point along the line:

We can determine if the plane faces the segment or not by evaluating the dot product of the plane’s normal, and the line segment’s direction vector.

From this we can determine which point of an intersecting line segment to influence. If the plane is facing the segment direction, then we can clip against the end point, otherwise we can clip against the start point.

As we are testing the intersection against a convex object we can simply keep clipping against each plane and altering the segment endpoints until we have the minimum remaining line length, or the intersection length becomes empty (there is no intersection).

In pseudo-code the entire operation is:

AB = B – A
tFirst = 0
tLast = 0
for all planes:
 denom = N dot AB
 dist = d – N dot A
 t = dist/denom
 if (denom>0 )
  if (t>tFirst) tFirst = t;
 else
  if (t if (tFirst>tLast)
  No Intersection