We want to control the hexapod machine using low cost pc hardware. We therefore need fast integer algorithms. The control strategy will be to map curvilinear motion of the platform joints in real 3-space to approximating linear segment motion in integer 3-space. Bresenham's well-known linear interpolation algorithm handles interpolation in 3-space very efficiently. It answers the question: if we require a step along a segment, must we step in x, y, z for best fit? An approach similar to Bresenham's circular interpolation algorithm provides an efficient mapping from 3-space to leg-space (s). It answers the question: if we require a step in x, y, z, must we step in s for best fit? It is an original algorithm, but I have no doubt others have found it too. It is shown below in two dimensional form for clarity, but expands easily to three dimensions. Apart from the best fit approximation inherent in an integer algorithm, it is exact. A squared form of length error is maintained and used for decision making.
The leg interpolation algorithm is based on sqr(x + 1) = sqr(x) + 2*x + 1. That is, if we are moving on an integer x grid, the difference between the squares on adjacent grid lines is simply 2*x + 1, where x is the smaller value. Extending this to an integer xy grid, the square of the length of the vector from the origin to the point (x, y) is sqr(x) + sqr(y). If we increment x by 1, this square changes by 2*x + 1. This gives us a fast way of keeping track of a squared vector length. Similarly, considering now an integer s grid along the leg, if we take a positive step in s, the square of the leg length changes by 2*s + 1. By comparing these squares, we can decide whether a step in x requires one in s for a best fit. To avoid very large integer values we use the difference of the squares, storing this in a variable indicated by [...] in the code fragment below.
Suppose a positive step in x is required:
[sqr(s) - sqr(x) - sqr(y)] = [sqr(s) - sqr(x) - sqr(y)] - (2*x + 1);
// new value of variable old value of variable old x
x = x + 1;
while ([sqr(s) - sqr(x) - sqr(y)] < 0) // max twice round loop
{
// take a step in s
[sqr(s) - sqr(x) - sqr(y)] = [sqr(s) - sqr(x) - sqr(y)] + 2*s + 1;
// new value of variable old value of variable old s
s = s + 1;
// issue hardware signal
}
 |
LME Hexapod Machine | |
Computer Craftsmanship |