Posted by anton

Spline curves February 05, 2010 07:46AM |
Registered: 9 years ago Posts: 94 |

BeagleFury wrote this in another thread:

That prompted me to do some thinking... about having a small MCU for each axis, responsible for controlling the motion of that one axis, where the control instruction would simply describe a spline, and the time to complete the motion. The step of all the axis would be synchronized via a central clock tick.

That started me on a hunt for known efficient algorithms for stepping through a cubic spline, and I found something which seems to be able to do this, the algorithm uses forward integration, and will always carry motion forward along the curve by 1 step; but... the algorithm is patented and requires a lookup table of 8kb. Fortunately the patent expires in 3 years, and the Sun didn't take out a patent in my country, so I can use it to my hearts content.

So my question is this: Is there a better algorithm for doing cubic spline stepping? if not, what would a good, cheap and small MCU for performing the calulations be?

QuoteBeagleFury

I based my brainstorming on the idea that from the host perspective, I probably want to have 5-10 pending requests always waiting to be sent to the firmware. Discarding and retransmitting all of those costs very little on the host (As the buffer size in firmware may be limited... at best case, it might have a 2 or 3 out of order reconstruction it could possibly do, but that makes it more complicated...)

I've also made statements assuming people already know what I'm working on. smiling smiley Sorry about that. The system I'm working on implements following spline curves on the firmware. My firmware will be GCode illiterate because it is too computational expensive to turn lines into a two linkage polar arm form. I've got the cubic spline math working at ~15 microseconds per spline step on an arduino mega; To drive a 5D robot, I'll need 5 splines per path descriptor (less than .1 milliseconds for spline stepping.) I believe doing it this way greatly simplifies how the firmware operates, reducing all motion to a 5 dimentional spline curve (2 polar arms, 1 linear arm, the extrusion 'position', and the temperature); my accuracy for transforming linear to polar depends completely on my bandwidth, and the fixed point accuracy for which I've coded the firmware; it is currently a 16 bit integer + 32 bit binary fraction (over 2^32), with ranges limiting some of the components (160 bits total for spine step state -- each step requires 16 single byte ADD or ADC operations on the data structure). Sorry if that is a bit complex, but I have difficultly describing it in words. The code will probably be shorter than the paragraph I wrote. smiling smiley

That prompted me to do some thinking... about having a small MCU for each axis, responsible for controlling the motion of that one axis, where the control instruction would simply describe a spline, and the time to complete the motion. The step of all the axis would be synchronized via a central clock tick.

That started me on a hunt for known efficient algorithms for stepping through a cubic spline, and I found something which seems to be able to do this, the algorithm uses forward integration, and will always carry motion forward along the curve by 1 step; but... the algorithm is patented and requires a lookup table of 8kb. Fortunately the patent expires in 3 years, and the Sun didn't take out a patent in my country, so I can use it to my hearts content.

So my question is this: Is there a better algorithm for doing cubic spline stepping? if not, what would a good, cheap and small MCU for performing the calulations be?

Re: Spline curves February 05, 2010 08:58AM |
Registered: 9 years ago Posts: 278 |

anton Wrote:

-------------------------------------------------------

> BeagleFury wrote this in another thread:

>

> {...}

>

> So my question is this: Is there a better

> algorithm for doing cubic spline stepping? if not,

> what would a good, cheap and small MCU for

> performing the calulations be?

See my blog post from a year ago...

I've used this technique since about mid-1990, though, for different polynomials (a quintic to do star bursts and lens flares quickly for a 3D game engine.)

-------------------------------------------------------

> BeagleFury wrote this in another thread:

>

> {...}

>

> So my question is this: Is there a better

> algorithm for doing cubic spline stepping? if not,

> what would a good, cheap and small MCU for

> performing the calulations be?

See my blog post from a year ago...

I've used this technique since about mid-1990, though, for different polynomials (a quintic to do star bursts and lens flares quickly for a 3D game engine.)

Re: Spline curves February 05, 2010 04:26PM |
Registered: 10 years ago Posts: 132 |

I found the Fixed point spine code I used in the PostScipt interpreter I wrote some 20+ years ago. I dug this out earler in the week when I was considering a more postscript like firmware. The code is fairly small so I will post it here. Note that the segment weight function could be pre loaded as it is in effect a table.

It is interesting, how the Write Brothers observed that when it comes time to bicycle, Many people will invent bicycles at the same time. I have been considering using the ATtiny25 chips to act as a curve spline controller. I almost created this sub topic last night.

-julie

Edited 1 time(s). Last edit at 02/05/2010 04:31PM by sheep.

It is interesting, how the Write Brothers observed that when it comes time to bicycle, Many people will invent bicycles at the same time. I have been considering using the ATtiny25 chips to act as a curve spline controller. I almost created this sub topic last night.

-julie

/* The greater the number of curve segments, the smoother the curve, and the longer it takes to generate and draw. The number below was pulled from a hat. It is best for printing. */ #define SEGMENTS 16 static Fixed weight1[SEGMENTS +1]; static Fixed weight2[SEGMENTS +1]; #define w1(s) weight1[ s] #define w2(s) weight2[ s] #define w3(s) weight2[SEGMENTS - s] #define w4(s) weight1[SEGMENTS - s] /* * SetupBezier - one time setup code. * Compute the weights for the Bezier function. * For Speed and space - Precompute this table. * */ void SetupBezier(void) { Fixed t, zero, one; int s; zero = FixRatio(0,1); one = FixRatio(1,1); weight1[0] = one; weight2[0] = zero; for (s = 1; s < SEGMENTS; ++s) { t = FixRatio(s, SEGMENTS); weight1[ s] = FixMul(one -t, FixMul(one - t, one - t)); weight2[ s] = 3 * FixMul(t, FixMul(t - one, t - one )); } weight1[SEGMENTS] = zero; weight2[SEGMENTS] = zero; } /* * compute segments for the Bezier curve, * since the curve touches the endpoints, the endpoints are not * computed. * */ static void computeSegments(p1, p2, p3, p4, segment) Point p1, p2, p3, p4; Point segment[]; { int s; segment[0] = p1; for (s = 1; s < SEGMENTS; ++s) { segment[ s].v = FixRound(w1(s) * p1.v + w2(s) * p2.v + w3(s) * p3.v + w4(s) * p4.v); segment[ s].h = FixRound(w1(s) * p1.h + w2(s) * p2.h + w3(s) * p3.h + w4(s) * p4.h); } segment[SEGMENTS] = p4; } /* * BezierCurve - * Draw a curve with the given endpoints(p1,p4), and the * given control points (p2,p3) * * This version does not handle the pen or the mode. * */ void BezierCurve(p1, p2, p3, p4) Point p1, p2, p3, p4; { int s; Point segment[SEGMENTS + 1]; computeSegments(p1, p2, p3, p4, segment); PushMove(segment[0].h, segment[0].v); for (s = 1; s <= SEGMENTS; ++s) { if (segment[ s].h != segment[s - 1].h || segment [ s].v != segment[s - 1].v ) { PushLine(segment[ s].h, segment[ s].v); } } }

Edited 1 time(s). Last edit at 02/05/2010 04:31PM by sheep.

Sorry, only registered users may post in this forum.