Revision as of 05:39, 1 August 2010

Project

This page is under construction ...

Introduction

What is my project all about? Well for my honours project I am looking at the performance of iterative inverse kinematic algorithms. Yes there are a few big words in that title so I will break it down and you will see that its not so bad.

My project focuses on the inverse kinematics of simple joint chains such as a robotic arm or the leg of an computer animated character. If we want to position the end of the robotic arm (end-effector) then we need to tell each joint in the arm to move to a particular angle. Once the robot arm has moved each of its joints to the required position the end-effector will (hopefully) be in the desired position. The hard part of this and coincidently that 'inverse' part of the title is finding out what angles you need at each joint so that the end-effector ends up at the correct location. Enter the CCD algorithm ...

The Cyclic Coordinate Descent (CCD) algorithm is an iterative algorithm that operates on a joint chain and works by converging the end-effector to the desired target location. The CCD algorithm is relativity simple to implement and this makes it very popular for use in the fields of robotics and computer animation and computer games.

Below are to images that will help clarify what the CCD algorithm achieves. The first image is the 'before' shot. The joint chain is stretched out straight with the base of the joint chain at the origin. The green circle is the target location and the red circle is the end-effector of the joint chain. The second image is the 'after' shot. In this second image we can see the result of running the CCD algorithm on the joint chain. You will note that the end-effector has moved to the target location. This is a pretty good indication that everything has gone smoothly in the algorithm, it has been able to find the rotation required for each joint in order hit the target.

The joint chain before is has moved to the target.

The joint chain after is has reached its target.

Ok so for each target we have a bunch of information regarding the behaviour of the CCD algorithm, these include the number of iterations done to get the end-effector to the target and others such as the total amount of rotation taken by all the joints. If we now use this information to colour the target and we make as many targets as there are pixels then we get a colourised map of performance of the algorithm with the joint chain. The result can be seen below.

Requirements

The program needs to able to render a metric map for a given size joint chain and a given iterative IK algorithm.

Input:

• Number of joints in the chain.
• Type of iterative IK algorithm (will be using at least two initially)
• Behaviour parameters for the algorithm, including:
  • Maximum number of iterations to attempt
  • Tolerance distance required for the end-effector to be considered at the target
• Size of the metric map (image dimentions size x size)
• Metric to display on the metric map

Output:

• Metric map (size x size) image
• Range of results for the rendered metric map

Initial Design

The initial design breaks the whole problem in smaller achievable problems. Each sub problem can be outline in a basic flow such as:

1. Create the required number of joints
2. Create a 2D buffer to hold the results, one element for each pixel/target
3. For each target in the buffer:
   1. Reset the joint chain to its default position
   2. Run the algorithm over the joint chain for this target
   3. Save the result to the buffer
4. Loop over the buffer and find the min and max (range) for the required metric
5. Create an image the same size as the buffer
6. For each element in the buffer:
   1. Use the resulting metric range to colourise the result
   2. Store the colour in the corresponding image pixel

This was broken down further into classes that took care of one piece of functionality only.

Link Class: This class represents a basic link (joint). It has a static length and the angle can be modified by the algorithm. The origin is location of the base of the link.

Solver Class: This abstract class must be inherited and the Solve() method overridden in order to compute the final solution for the joint chain.

UML Diagram