Circular Motion in 2D for graphics and robotics

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).

1. 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);
   

2. 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.
   
3. 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

• 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

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

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.