GPU and Graphics catchup post

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

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

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

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

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

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

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:

• CAT 'command' system for haul trucks and MineGem. (See CSIRO's work on LHD)
  
• Atlas-Copco scooptram for loaders (See Joshua Marshall's work on Scooptram)
  
• Sanvik Automine for loaders.
  

Mozilla Demopart - The Self Explanatory Demo

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

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

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

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:

1. Integrated middlewear for a larger package
   
2. (hard) Real time control orientated frameworks
   
3. (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.

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

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

'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);

r1

So why does it look the way it looks?

r2

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)

Your browser doesn't appear to support the HTML5 <canvas> element.

Demoparties

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

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

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

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

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: