XY positioning algorithm needed

[Tracid]

Hi everybody!
My project doesnt involves a CNC project but a part of it needs some solution which i think is related to CNC.
So, i would like to develop an intelligent lighting effect( the type name is
Scanner )
I dont know if you know them or no so i describe the problem-part mechanics of it.
The light comes out through optics and a small mirror reflects the beam the
direction the motors move.
So i have two motors,one rotates the second and the mirror is attached on
the second motor.That way X and Y axis rotation is achieved.First motor
rotates X axis and the second Y axis.
(i found a picture on the net so i attached for better understanding)

And here comes the problem:

the full range of X axis is about 180degrees, the full range of Y axis is
90degrees. (the degrees are implemented as number of maximum steps from one
edge/limit to the other edge/limit)

I am using a microcontroller with 8 bit registers ( PIC ) so i can break down each
range(X and Y) into 256 positions.At the system reset the motors find their
zero positions (0,0) and all the following desired positions are searched
relatively to the actual position.

You can imagine as my application have to draw fine lines from point A to
point B.So with a fast uCPU the motion should look smooth.
Since i am not an experienced hobbyst yet,i asked you for a solution.
I found on the web a method called linear interpolation,circular
interpolation.The problem is that i found only one document covering both
with minimal extension.

What i think:
linear interpolation means that only one motor moves at a time and one motor
moves smaller lenghts while the other moves bigger lenghts(assuming the
destinations are not the same distance) and the move ´enable´ is switched
between each other.(like in paint: line from point A to B consists of longer lines-shorter lines)
I think this way if the motors are moving at very low speed i can see the
inaccuracy in moving and instead of the pretty (ideal) straight line i see
´stairs´ (stairway, stairy moving - sorry my English)
This is the right way i think?

What i need:
i thought about using two separate Timer modules for both motors and
instead of switching the move between them , rotate both at the same time
and for the same time but with different speed.So if X motor have to move
100 positions and Y motor have to move only 50 positions that means X have
to do two times more and thus it have to move two times faster if i want
them to arrive at the destination at the same time.(so timer interrupts move the motors some steps)
I also have to place into account that theres a desired avarage(or
reference) speed at which one motor moves and the second motors speed is
referenced to this value.

So this is the description of my problem.
Since you are familiar with CNCs i thought maybe you can recommend me some ideas.
My application is very time-sensitive so i must avoid mathematical
calculations which steal a lot of processing time.

Every idea is welcome!

Thanks!

[DR-Motion]

<snip>


I am using a microcontroller with 8 bit registers ( PIC ) so i can break down each
range(X and Y) into 256 positions.At the system reset the motors find their
zero positions (0,0) and all the following desired positions are searched
relatively to the actual position.



What i need:
i thought about using two separate Timer modules for both motors and
instead of switching the move between them , rotate both at the same time
and for the same time but with different speed.So if X motor have to move
100 positions and Y motor have to move only 50 positions that means X have
to do two times more and thus it have to move two times faster if i want
them to arrive at the destination at the same time.(so timer interrupts move the motors some steps)
I also have to place into account that theres a desired avarage(or
reference) speed at which one motor moves and the second motors speed is
referenced to this value.

So this is the description of my problem.
Since you are familiar with CNCs i thought maybe you can recommend me some ideas.
My application is very time-sensitive so i must avoid mathematical
calculations which steal a lot of processing time.

<snip>

!

Yes, this is good thinking.

Do a search on phase accumulators for the background but basically...

if you have a finite sized accumulator (i.e. adder register) and add a smaller or same sized value to it at regular intervals it will overflow at a frequency equal to the ratio of 2 raised to the power of the register size, to the addend. The overflow (carry out) can be used as a step signal for your axis.

For example, using an 8 bit accumulator, add 3 to the accumulating sum once every millisecond and the carry out from the accumulator will occur every 256/3 milliseconds.

similarily by adding 256 every millisecond you will have a step every 256/256=1 millisecond.

Note that the frequency resolution is 1 bit :-)

The computational overhead involves a load register, an add, a branch if carry set, and an output bit.... very fast ;-)
<edit added>
Also note that the vector velocity(below) is only calculated once before the relatively long (time) move.

So to succesfully interpolate your two axes:

1. select a maximum velocity and use as the frequency of your interrupt timer.

2. calculate the vector velocity = feedrate / sqrt((dist X * dist X) + (dist Y * dist Y)).

so that feed X = dist X * vector velocity
and feed Y = dist Y * vector velocity

3. use an X and a Y accumulator in your interrupt routine to sum feed X and feed Y

4. track your distance travelled to end motion with a zero velocity input.
The motion will complete approximately simultaneously within the tolerances of your arithmetic.

[ViperTX]

Bresenham Alogrithm

[Tracid]

Thanks DR-Motion!
I think this is what i really want(the result)!
But one wrong thing is with this idea(for me!) : it uses sqrt and division and this is what i cant afford.
I saw a project somewhere which have to accomplish the same jobs as mine and the CPU runs at only 16MHz and mine will at 20MHz.But this is still slow for such calculations.
So theres another way.

Lets say i will use lookup tables since there is a little finite of combinations of distance differences ( total of 256 ) between X and Y.
I calculate the values with my calculator or Excel for a specified speed.Yes,then i can use it to jump to the location in the lookup table according to the distance difference.for example if no difference between them then add zero to the PCL and read the value then store it as speed for the first motor.The second motors speed is constant.

But a problem takes place when i want to use different speeds.I mean the DMX controller console tells my equipment the speed(the reference or avarage speed).It would last till silvester 2007 to create lookup tables for all the 256 possible speed levels.And its absolutely meaningless to use such a big memory place.
Since i am using integer numbers only(so i round up and down in calculations) there will be some offset errors(caused by rounding) if using only one lookup table and use only additions to get the correct speed offset from the original.
I hope you understand what i mean! how to compensate for it?

[Tracid]

I understand your algorithm Dr Motion,and yes,its the one i need.

You wrote its very fast- could you please explain me how do you mean that?

My uCPU is running at 40MHz and has a multiplication instruction only(no division,sqrt)

Could you please explain me deeper how to do it fast?
Approximate cycles?

Thanks!